2357: 【例】【入门】城市之间的最短路(2044)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：12
解决：6
题目描述
小丁同学准备去A国旅游，他买了一张A国的地图，地图标出了A国著名的 个旅游热门城市，并标注了这 个城市之间有 条路线相连以及每条路线的长度。
请你编程帮助小丁求出其中两个城市之间的最短距离。
输入
输入第一行为两个正整数 （）和 （）， 表示城市个数， 表示线段个数。
接下来 行，每行输入三个整数 和 ，表示 市与 市之间存在一条线段，线段长度为 。（ 与 不同，且本题的数据中两个城市之间最多只有一条路）
每组最后一行输入两个整数 和 ，表示问题： 市与 市之间的最短距离是多少。（ 与 不同）
城市标号为 ， 。
输出
输出 市与 市之间的最短距离，如果 市与 市之间非连通，则输出
No path。样例输入 复制
4 4
1 2 4
1 3 1
1 4 1
2 3 1
2 4样例输出 复制
3提示
#include<bits/stdc++.h>
using namespace std;
const int MAXN=110;
const int INF=0x3f3f3f3f;
int n,m,s,t;
struct edge{
int to,len;
};
int d[MAXN];
bool f[MAXN];
vector<edge> p[MAXN];
void dijkstra(){
memset(d,0x3f,sizeof(d));
d[ s ]=0;
for(int i=1;i<=n;i++){
int mi=-1;
for(int j=1;j<=n;j++){
if(!f[j]&&(mi==-1||d[j]<d[mi])){
mi=j;
}
}
f[mi]=true;
for(int j=0;j<p[mi].size();j++){
int to=p[mi][j].to;
if(!f[to]&&d[mi]+p[mi][j].len<d[to]){
d[to]=d[mi]+p[mi][j].len;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x=0,y=0,l=0;
cin>>x>>y>>l;
p[x].push_back((edge){y,l});
p[y].push_back((edge){x,l});
}
cin>>s>>t;
dijkstra();
if(d[t]!=INF) cout<<d[t];
else cout<<"No path";
return 0;
}