【题解】PAT 1003 Emergency
主要思路：Dijkstra + DP
如果做过最短路计数，这道题就相当于双倍经验了。
就是在跑Dijkstra时，另计一个 \(t_i\) 作为到第 \(i\) 个点时最短路的条数，一个 \(rs_i\) 作为到第 \(i\) 个点最短路点权和的最大值
注意一下维护条数时要分类，是不是 \(dis\) 更新了，更新了要用新值覆盖掉之前的数值。
还有，点的编号 \(0\) ~ \(n-1\)，边是双向边，千万别搞错了
部分代码：
struct wtf{
int t,r,rs;
}r[505];
struct node{
int u,d;
friend bool operator<(const node &a,const node &b){
return a.d>b.d;
}
};
void Dijkstra(){
for(int i=0;i<=n-1;i++) dis[i]=inf;
dis[c1]=0, r[c1].t = 1;
priority_queue<node>q;
node x;
x.u=c1,x.d=0;
q.push(x);
while(!q.empty()) {
node fr = q.top();
q.pop();
int u = fr.u, d = fr.d;
if(d != dis[u]) continue;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to, w = e[i].w;
if(dis[u] + w <= dis[v]) {
bool flag = 0;
if(dis[u] + w < dis[v])
r[v].t = r[u].t,
flag = 1;
else if(dis[u] + w == dis[v])
r[v].t = r[v].t + r[u].t;
r[v].rs = max(r[u].rs + r[v].r, r[v].rs);
dis[v] = dis[u] + w;
if(flag) {
node y;
y.u = v, y.d = dis[v];
q.push(y);
}
}
}
}
} P.S. ：帮人改代码时看到的题，高三里第一次敲代码，，，高三继续加（tui）油（fei）！
查看24道真题和解析
