UVALive 6885 Flowery Trails 最短路枚举

题目连接：

　　http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=129723

题意：

　　给你一个n点m图的边

　　1到n有多条最短路，问你所有经过的边的总和*2是多少

题解：

　　对1,n分别求单源最短路径上spfa

　　枚举某条边是否为最短上的边

　　　即 边权+disA[i] + disB[i] = 最短路长度，就是答案

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+20, M = 1e6+10, mod = 1e9+7, inf = 1e9+1000;
typedef long long ll;

int head[N],t,vis[N],dis[N],n,m,disA[N],disB[N];
struct edge{int to,value,next;}e[N*2];

void add(int u,int v,int w) {e[t].next=head[u],e[t].to=v,e[t].value=w;head[u]=t++;}

void init(){
    t = 0;
    memset(head,-1,sizeof(head));
}

void spfa(int u) {
    for(int i=1;i<=n;i++) dis[i] = inf, vis[i] = 0;
    vis[1] = 1;
    dis[u] = 0;
    queue<int> q;
    q.push(u);
    while(!q.empty()) {
        int k = q.front();q.pop();
        vis[k] = 0;
        for(int i=head[k];i!=-1;i=e[i].next) {
            int to = e[i].to;
            if(dis[k] + e[i].value < dis[to]) {
                dis[to] = dis[k] + e[i].value;
                if(!vis[to]) {
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        init();
        for(int i=1;i<=m;i++) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a++,b++;
            add(a,b,c);
            add(b,a,c);
        }
        spfa(1);
        for(int i=1;i<=n;i++) disA[i] = dis[i];
        spfa(n);
        for(int i=1;i<=n;i++) disB[i] = dis[i];
        int mx = dis[1];
        ll ans = 0;
        for(int i=1;i<=n;i++) {
            for(int j=head[i];j!=-1;j=e[j].next) {
                int to = e[j].to;
                int value = e[j].value;
                if(disA[i] + disB[to] + value == mx) ans+=value;
            }
        }
        printf("%lld
",2ll*ans);
    }
}