#include<bits/stdc++.h> using namespace std; const int N=510,M=100010; 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 数组的各个元素初始化为无穷大 memset(dist,0x3f,sizeof dist); // 源点到源点的距离为0 dist[x]=0; // 分别处理每个点的问题 for(int i=0;i<n;i++){ int t=-1; // 贪心策略找一个最短距离的点 // 遍历 dist 数组，找到一个没有确定最短路径的节点，并且是距离源点最近的点 t for(int j=1;j<=n;j++){ if(!state[j] && (t==-1 || dist[j]<dist[t])) t=j; } if(t==y) return; // 标记该 t 点已经被处理 state[t]=1; // 遍历 t 点可以到达的所有节点v for(int j=h[t];j!=-1;j=ne[j]){ int v=e[j]; // 更新节点v到源点的距离 dist[v]=min(dist[v],dist[t]+w[j]); } } } int main(){ memset(h,-1,sizeof h); // 邻接表初始化 cin>>n>>m; // 读取每条边的数据 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]; else cout<<"No path"; return 0; }