poj 3463 Sightseeing

poj 3463 Sightseeing

#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#define MAXN 1005#define MAXM 500005#define INF 1000000000using namespace std;struct node{    int v, next, w;}edge[MAXM];int d[MAXN][2], e, n, m;int cnt[MAXN][2];int head[MAXN];bool vis[MAXN][2];void init(){    e = 0;    memset(head, -1, sizeof(head));}void insert(int x, int y, int w){    edge[e].v = y;    edge[e].w = w;    edge[e].next = head[x];    head[x] = e++;}int dijkstra(int s, int t){    int flag, u;    memset(vis, 0, sizeof(vis));    memset(cnt, 0, sizeof(cnt));    for(int i = 1; i <= n; i++)        d[i][0] = d[i][1] = INF;    cnt[s][0] = 1;    d[s][0] = 0;    for(int i = 1; i < 2 * n; i++)    {        int mini = INF;        for(int j = 1; j <= n; j++)        { if(!vis[j][0] && d[j][0] < mini) {     u = j;     flag = 0;     mini = d[j][0]; } else if(!vis[j][1] && d[j][1] < mini) {     u = j;     flag = 1;     mini = d[j][1]; }        }        if(mini == INF) break;        vis[u][flag] = 1;        for(int j = head[u] ; j != -1; j = edge[j].next)        { int w = edge[j].w; int v = edge[j].v; if(d[v][0] > mini + w) {     d[v][1] = d[v][0];     cnt[v][1] = cnt[v][0];     d[v][0] = mini + w;     cnt[v][0] = cnt[u][flag]; } else if(d[v][0] == mini + w) cnt[v][0] += cnt[u][flag]; else if(d[v][1] > mini + w) {     d[v][1] = mini + w;     cnt[v][1] = cnt[u][flag]; } else if(d[v][1] == mini + w) cnt[v][1] += cnt[u][flag];        }    }    int ans = 0;    if(d[t][1] == d[t][0] + 1) ans = cnt[t][1] + cnt[t][0];    else ans = cnt[t][0];    return ans;}int main(){    int s, t, T, x, y, w;    scanf("%d", &T);    while(T--)    {        init();        scanf("%d%d", &n, &m);        for(int i = 1; i <= m; i++)        { scanf("%d%d%d", &x, &y, &w); insert(x, y, w);        }        scanf("%d%d", &s, &t);        printf("%dn", dijkstra(s, t));    }    return 0;}