poj 1511 Invitation Cards 静态邻接表的SPFA

本文主要是介绍poj 1511 Invitation Cards 静态邻接表的SPFA，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//用vector写邻接表无情的TLE，只好用静态邻接表，两次SPFA分别求去和回的最短路

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1000005;
int n, m, d[maxn], pre[2][maxn], inqueue[maxn], cnt;
struct node{
     int v, w, next;
}edge[2][maxn];
void add_edge(int s, int e, int w){
    edge[0][cnt].v=e;
    edge[0][cnt].w=w;
    edge[0][cnt].next=pre[0][s];
    pre[0][s]=cnt;
    edge[1][cnt].v=s;
    edge[1][cnt].w=w;
    edge[1][cnt].next=pre[1][e];
    pre[1][e]=cnt;
    cnt++;
}

void init(){
    int i, x, y, c;
    cnt=1;
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        pre[0][i]=-1;
        pre[1][i]=-1;
    }
    for(i=0; i<m; i++){
        scanf("%d%d%d", &x, &y, &c);
        add_edge(x, y, c);
    }
}

bool spfa(int g, int st){
    int i, head, s;
    for(i=1; i<=n; i++){
        inqueue[i]=0;
        d[i]=INF;
    }
    queue<int > q;
    d[st]=0;
    inqueue[st]=1;
    q.push(st);
    while(!q.empty()){
        head=q.front();
        q.pop();
        inqueue[head]=0;
        s=pre[g][head];
        while(s!=-1){
            if(d[edge[g][s].v]>d[head]+edge[g][s].w){
                d[edge[g][s].v]=d[head]+edge[g][s].w;
                if(!inqueue[edge[g][s].v]){
                     inqueue[edge[g][s].v]=1;
                     q.push(edge[g][s].v);
                }
            }
            s=edge[g][s].next;
        }
    }
    return true;
}

int main(){
    //freopen("1.txt", "r", stdin);
    int i, j, T;
    long long ans;
    scanf("%d", &T);
    while(T--){
    init();
    ans=0;
    for(i=0; i<2; i++){
        spfa(i, 1);
        for(j=2; j<=n; j++)
        ans+=d[j];
    }
    printf("%lld\n", ans);
    }
    return 0;
}