POJ 3463: Sightseeing

タイトルリンク:http://poj.org/problem?id=3463
タイトル:
方向図が与えられ、
始点から終点までの間を求めて、
最短パスと最短パスの長さに1を加えたパスは全部でいくつかあります.
アルゴリズム:
dijkstraアルゴリズムのいくつかの変形.
各ポイントについて、始点、終点から終点までの最短パス長、および最短パス数を前処理します.
次に、最短パスにある各ポイントについて、
彼のあるエッジでは、最短のパスの長さよりも1つのパスを得ることができます.
すると、前処理によれば、この辺を通る同じ長さが最短経路長より1つ加算された経路が何本あるかが得られる.
コードは次のとおりです.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

typedef pair<int,int> PII;
const int MAXN=1100;
const int MAXM=30000;
int head[MAXN];
int d1[MAXN],d2[MAXN],cot1[MAXN],cot2[MAXN];
int to[MAXM],nxt[MAXM],w[MAXM];
int E;

struct cmp {
    bool operator ()(const PII& a, const PII& b) {
        return a.second>b.second;
    }
};
priority_queue <PII,vector<PII>,cmp> q;

void _addedge(int u, int v, int val) {
    to[E]=v;
    nxt[E]=head[u];
    w[E]=val;
    head[u]=E++;
}

void addedge(int u, int v, int val) {
    _addedge(u,v,val);
    _addedge(v,u,val);
}

void dijkstra(int s, int t, int d[],int cot[],int flg) {
    d[s]=0;
    cot[s]++;
    while(!q.empty()) {
        q.pop();
    }
    q.push(make_pair(s,0));
    while(!q.empty()) {
        int u=q.top().first;
        int temp=q.top().second;
        q.pop();
        if(temp!=d[u]) {
            continue;
        }
        for(int i=head[u]; i!=-1; i=nxt[i]) {
            if((i&1)!=flg) {
                continue;
            }
            int v=to[i];
            if(d[v]==-1||d[v]>d[u]+w[i]) {
                d[v]=d[u]+w[i];
                q.push(make_pair(v,d[v]));
                cot[v]=cot[u];
            } else if(d[v]==d[u]+w[i]) {
                cot[v]+=cot[u];
            }
        }
    }
}

int cal(int n, int totdis, int flg) {
    int ans=0;
    for(int u=0; u<n; u++) {
        if(d1[u]+d2[u]>totdis) {
            continue;
        }
        for(int i=head[u]; i!=-1; i=nxt[i]) {
            if((i&1)!=flg) {
                continue;
            }
            int v=to[i];
            if((d1[u]+w[i]+d2[v]==totdis+1)) {
                ans+=cot1[u]*cot2[v];
            }
        }
    }
    return ans;
}

int main() {
    int cas;
    scanf("%d",&cas);
    while(cas--) {
        int n,m;
        scanf("%d%d",&n,&m);
        E=0;
        memset(head,-1,sizeof(head));
        memset(d1,-1,sizeof(d1));
        memset(d2,-1,sizeof(d2));
        memset(cot1,0,sizeof(cot1));
        memset(cot2,0,sizeof(cot2));
        while(m--) {
            int u,v,val;
            scanf("%d%d%d",&u,&v,&val);
            u--;
            v--;
            addedge(u,v,val);
        }
        int s,t;
        scanf("%d%d",&s,&t);
        s--;
        t--;
        dijkstra(s,t,d1,cot1,0);
        dijkstra(t,s,d2,cot2,1);
        printf("%d
",cal(n,d1[t],0)+cot1[t]);
    }
    return 0;
}