1003 Emergency (25point(s))

Dijkstra最短路变体。

关键符号说明：

#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
using namespace std;

typedef pair<int,int> pii;
#define mp(x,y) make_pair((x),(y))

const int MAXN=500,MAXM=MAXN*MAXN,INF=0x3f3f3f3f;
int N,M,c[MAXN+1][MAXN+1],S,T,v[MAXN+1],dc[MAXN+1],dv[MAXN+1],cnt[MAXN+1];

int main(void) {
//    freopen("in.txt","r",stdin);
    scanf("%d%d%d%d",&N,&M,&S,&T);
    for(int i=0; i<N; i++)
        scanf("%d",&v[i]);
    memset(c,INF,sizeof c);
    int from,to,cost;
    for(int i=0; i<M; i++) {
        scanf("%d%d%d",&from,&to,&cost);
        c[from][to]=cost;
        c[to][from]=cost;
    }
    priority_queue<pii,vector<pii>,greater<pii> > q;
    memset(dc,INF,sizeof dc);
    dc[S]=0;
    dv[S]=v[S];
    cnt[S]=1;
    q.push(mp(0,S));
    int dist;
    while(!q.empty()) {
        from=q.top().second;
        dist=q.top().first;
        q.pop();
        if(dist!=dc[from])
            continue;
        for(to=0; to<N; to++){
            if(c[from][to]==INF) continue;
            if(dc[to]>dc[from]+c[from][to]) {
                dc[to]=dc[from]+c[from][to];
                dv[to]=dv[from]+v[to];
                cnt[to]=cnt[from];
                q.push(mp(dc[to],to));
            } else if(dc[to]==dc[from]+c[from][to]) {
                cnt[to]=cnt[to]+cnt[from];
                dv[to]=max(dv[to],dv[from]+v[to]);
            }
        }
    }
    printf("%d %d\n",cnt[T],dv[T]);
    return 0;
}

/*
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output:
2 4
*/