这道题纯属是一个裸的SPFA；
建议先把模板AC之后再做。
只需要做一些手脚，就是在加边的时候加一个双向边就好。
然后再第一次加点的时候
看不懂模板的出门左转度娘。
推荐下面一片讲解：
友链
所以说，直接上代码。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<queue> using namespace std; struct data{ int v;int next; int value; }edge[500010];//临界链表存变 int cnt; int alist[10010]; void add(int u,int v,int value) { edge[++cnt].v=v; edge[cnt].value=value; edge[cnt].next=alist[u]; alist[u]=cnt; return ; }//加边 queue<int> q; bool ins[10010]; int d[10010]; void spfa(int x)//跑一边SPFA，原理在上面 { d[x]=0; q.push(x); ins[x]=true; while(!q.empty()) { int now=q.front(); q.pop();ins[now]=false; int next=alist[now]; while(next) { int v=edge[next].v; int value=edge[next].value; if(d[v]>d[now]+value) { d[v]=d[now]+value; if(!ins[v]) { q.push(v); ins[v]=true; } } next=edge[next].next; } } return ; } int m,n,s,e; int main() { scanf("%d%d%d%d",&m,&n,&s,&e);//输入 for(int i=1;i<=n;i++) { int u,v,value; scanf("%d%d%d",&u,&v,&value); add(u,v,value);//加边 add(v,u,value);//反向边 } for(int i=0;i<=m;i++) d[i]=0x3f3f3f3f;//初始化 spfa(s);//跑SPFA printf("%d",d[e]);//输出 return 0;//程序拜拜 }