最短路-SPAF模板

以hdu1874畅通工程续为例

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 1005;
vector<pair<int, int> > E[maxn];
int d[maxn], inq[maxn];
int n, m,s,t;

void SPFA(int s)
{
    queue<int> Q;
    Q.push(s); d[s] = 0, inq[s] = 1;
    while (!Q.empty())
    {
        int now = Q.front(); Q.pop();
        inq[now] = 0;
        for (int i = 0; i < E[now].size(); i++) {
            int v = E[now][i].first;
            if (d[v] > d[now] + E[now][i].second)
            {
                d[v] = d[now] + E[now][i].second;
                if (inq[v] == 1) continue;
                inq[v] = 1;
                Q.push(v);
            }
        }
    }
}

int main()
{
    while (scanf("%d%d",&n,&m)==2)
    {
        for (int i = 0; i < maxn; i++) {
            E[i].clear(); inq[i] = 0, d[i] = 1e9;
        }
        for (int i = 0; i < m; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            E[x].push_back(make_pair(y, z));
            E[y].push_back(make_pair(x, z));
        }
        scanf("%d%d", &s, &t);
        SPFA(s);
        if (d[t] == 1e9)
            printf("-1\n");
        else
            printf("%d\n", d[t]);
    }
    return 0;
}