本文共 1136 字，大约阅读时间需要 3 分钟。
这道题纯属是一个裸的SPFA；
建议先把模板AC之后再做。只需要做一些手脚，就是在加边的时候加一个双向边就好。然后再第一次加点的时候看不懂模板的出门左转度娘。推荐下面一片讲解：所以说，直接上代码。#include#include #include #include #include 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 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;//程序拜拜}
转载地址：http://sglfm.baihongyu.com/