題目描述
有n座城市,編號從1到n
m條路,每條路都是單行的，即有一條從1到2的路,那么你可以從1到達2,但不能從2到達1
每條路都有一定的距離
給你起點和終點,求最短距離
可能包含重邊,也就是說從A到B可能會有多條長度不同路
輸入格式
第一行兩個整數n和m
第二行兩個整數s和t,表示起點和終點
接下來又m行,每行三個整數ui,vi,wi,表示有一條從城市ui到達vi的路,長度為wi
輸出格式
輸s到t的最短距離
如果不存在請輸出todokanaikoi
樣例輸入
3 3
1 2
1 3 1
3 1 2
3 2 5
樣例輸出
6
提示
1<=n<=1000
1<=m<=n*n
1<=wi<=1000
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct edge{
int y,w;
edge(int yy=0,int ww=0){
y=yy;
w=ww;
}
};
const int MAX=1010;
vector<edge> g[MAX];
bool vis[MAX];
int dis[MAX];
int main(){
int n,m,st,ed;
cin>>n>>m>>st>>ed;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
g[x].push_back(edge(y,w));
}
//dijkstra();
memset(vis,false,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[st]=0;
for(int i=1;i<=n;i++){
int id=0;
for(int j=1;j<=n;j++)
if(vis[j]==false&&dis[j]<dis[id])
id=j;
if(id==0)
break;
vis[id]=true;
for(int j=0;j<g[id].size();j++){
int y=g[id][j].y;
int w=g[id][j].w;
if(dis[y]>dis[id]+w)
dis[y]=dis[id]+w;
}
}
if(vis[ed]==true)
cout<<dis[ed]<<endl;
else
cout<<"todokanaikoi"<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277418.html
標籤：其他