这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
这是以前用Dijkstra做的。
http://www.wutianqi.com/?p=1894
现在用SPFA再做一次~~~
// HDOJ 1874 SPFA
#include
using namespace std;
const int MAXN = 1005;
const int INF = 99999;
//用数组实现邻接表存储,pnt[i,0]表示与i相邻的结点个数,pnt[i,1...k]存储与i相邻的点
//int pnt[MAXN][MAXN];
int map[MAXN][MAXN]; //map[i,j]为初始输入的i到j的距离,并且map[i,i]=0;未知的map[i,j]=INF;
int dis[MAXN];
char vst[MAXN];
int Q[MAXN];
int SPFA(int n, int s)
{
int i, pri, end, p, t;
memset(vst, 0, sizeof(vst));
for(int i=0; i> N >> M)
{
for(int i=0; i> p >> q >> len;
if(len < map[p][q])
map[p][q] = map[q][p] = len;
}
cin >> start >> end;
SPFA(N, start);
if(dis[end] < INF)
cout << dis[end] << endl;
else
cout << -1 << endl;
}
return 0;
}