1003 Emergency (25point(s))
2020-02-28 本文已影响0人
iphelf
Dijkstra最短路变体。
关键符号说明：
| Symbol | Explanation |
|---|---|
| c | Cost (length) of an edge (road) |
| v | Value (amount of rescue teams) of a node (city) |
| d | Distance from source node to any other node |
| dc | Accumulated cost from source node to any other node |
| dv | Accumulated value from source node to any other node |
| S | Source |
| T | Target |
| q | Queue of nodes to be processed subsequently |
#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
*/
