Blog·Tanky WooABOUTRSS

HDU/HDOJ 1874 畅通工程续(SPFA)

03 Apr 2011
这篇博客是从旧博客 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;
}