#include<bits/stdc++.h> using namespace std; const int N=200,M=1000; // 使用邻接表进行图的存储 int h[N],e[M],ne[M],w[M],idx; int state[N]; // 点是否已经确定的状态 int dist[N]; // 各点到源点的最短路径长度 int n,m; void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void Dijkstra(int x,int y){ // 由于会存在多组数据，所以dist和state数组都需要进行初始化操作 memset(dist,0x3f,sizeof dist); memset(state,0,sizeof state); // 源点到源点的距离为0 dist[x]=0; // 分别处理未确定的各点到源点的操作 for(int i=1;i<=n;i++){ // 通过贪心策略找到一个未确定的点中距离源点最近的点 int t=-1; for(int j=1;j<=n;j++){ if(!state[j] && (t==-1 || dist[j]<dist[t])) t=j; } // 如果本次找到的点刚好为y，则直接返回，不需要再对后面的进行处理 if(t==y) return; // 标记t点为已经确认的点 state[t]=1; // 遍历t点能够达到的所有的点，并对该点进行松弛(三角不等式)操作 for(int j=h[t];j!=-1;j=ne[j]){ int v=e[j]; // 三角不等式更新 dist[v]=min(dist[v],dist[t]+w[j]); } } } int main(){ while(scanf("%d%d",&n,&m)!=EOF) { // end of file // 初始化新的邻接表的头节点 memset(h,-1,sizeof h); // 读取每一条边 while(m--){ int a,b,w; cin>>a>>b>>w; add(a,b,w),add(b,a,w); } int x,y; cin>>x>>y; Dijkstra(x,y); if(dist[y]!=0x3f3f3f3f) cout<<dist[y]<<endl; else cout<<"No path"<<endl; } return 0; }