以hud畅通工程为例：用ford暴力也可ac

样例的图解：

 

spfa算法模板，用一个数组来储存从开始的点到其他点的距离，不断进行松弛操作。

还有用队列来保存与其相邻的点。

void spfa(){    q.push(1);    dis[1] = 0;    vis[1] = 1;    while(!q.empty())    {        int u = q.front();        q.pop();        vis[u] = 0;        for(int i = head[u]; i != -1; i = e[i].next)        {            int v = e[i].v;            if(dis[v] > dis[u] + e[i].w)            {                dis[v] = dis[u] + e[i].w;                if(!vis[v])                {                    vis[v] = 1;                    q.push(v);                }            }        }    }}

 

 

附代码：

#include <iostream>

#include <queue>

#include<cstring>

#define mem(a,b) memset(a,b,sizeof(a))

#define inf 0x3f3f3f3f

using namespace std;

int save[220][220];

int n,m;

bool vis[220];

int d[220];

int spfa(int s,int t){

mem(vis,false);

mem(d,0x3f);

queue<int> q;

q.push(s);

d[s]=0;

vis[s]=true;

while(!q.empty()){

int c=q.front();

q.pop();

vis[c]=false;

for(int i=0;i<n;i++)

{

if(d[i]>d[c]+save[c][i])

{

d[i]=d[c]+save[c][i];

if(!vis[i])

{

vis[i]=true;

q.push(i);

}

}

}

}

if(d[t]>=inf)

return -1;

return d[t];

}

int main()

{

while(cin>>n>>m)

{

memset(save,0x3f,sizeof(save));

for(int i=0;i<m;i++)

{

int t1,t2,t3;

cin>>t1>>t2>>t3;

if(save[t1][t2]>t3)

{

save[t1][t2]=t3;

save[t2][t1]=t3;

}

}

int s,t;

cin>>s>>t;

cout<<spfa(s,t)<<endl;

}

}