查SPFA的資料時(shí)偶爾看到一種運(yùn)用，然后很淡定的敲之1A了

15MS+328k?? code:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 207;
const int inf = 100000000;

int vis[N], map[N][N];
int dis[N], q[N];

void spfa(int n, int s)
{
int i, f, r, p;
memset(vis, 0, sizeof(vis));
for(i = 0; i < N; i++)
q[i] = 0;
for(i = 0; i < n; i++)
dis[i] = inf;
dis[s] = 0; vis[s] = 1;
q[0] = s; f = 0; r = 1;
while(f < r)
{
p = q[f];
for(i = 0; i < n; i++)
if(dis[i] > map[p][i] + dis[p])
{
dis[i] = map[p][i] + dis[p];
if(!vis[i])
{
q[r++] = i;
vis[i] = 1;
}
}
vis[p] = 0;
f++;
}
}

int main()
{
int n, m, i, j, a, b, c;
//freopen("data.in", "r", stdin);
while(~scanf("%d%d", &n, &m))
{
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
map[i][j] = inf;
if(i == j) map[i][j] = 0;
}
while(m--)
{
scanf("%d%d%d", &a, &b, &c);
if(c < map[a][b])
map[a][b] = map[b][a] = c;
}
scanf("%d%d", &a, &b);
spfa(n, a);
if(dis[b] < inf)
printf("%d\n", dis[b]);
else
printf("-1\n");
}
return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/vongang/archive/2011/08/16/2141334.html

總結(jié)

以上是生活随笔為你收集整理的HDU_1874 畅通工程续(SPFA)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。