1003 Emergency (25 分)

题目链接

一、算法分析

从终点跑一次dijikstra最短路，并在路途中计算最短路的条数和路径上可选择的救援队伍最大值。
关键的两处处理就在：

if(dis[u] + w < dis[v]){
	dis[v] = dis[u] + w;
	num_trace[v] = num_trace[u];
	num_rescue[v] = num_rescue[u];
	que.push(make_pair(-dis[v], v));
}
else if(dis[u] + w == dis[v]){
	num_trace[v] += num_trace[u];
	num_rescue[v] = max(num_rescue[u], num_rescue[v]);
}
num_trace 最短路的条数
num_rescue 救援队伍数量最大值

二、测试点

我错在234的原因是，读错了题，对于救援队伍数量的最大值，指的是一条最短路上的救援队伍，我理解成了所有条最短路，因此出错。
错误代码片段：

else if(dis[u] + w == dis[v]){
	num_trace[v] += num_trace[u];
	num_rescue[v] += num_rescue[u];
}

正确代码片段：

else if(dis[u] + w == dis[v]){
	num_trace[v] += num_trace[u];
	num_rescue[v] = max(num_rescue[u], num_rescue[v]);
}

三、代码实现

#include<bits/stdc++.h>
using namespace std;
#define N 505
vector< pair< int, int > >vec[N];
priority_queue< pair< int , int> >que;
int restot[N];
int vis[N], dis[N], num_trace[N], num_rescue[N];
void dijikstra(int origin){
	memset(dis, 63, sizeof(dis));
	que.push(make_pair(0, origin));
	dis[origin] = 0;
	num_trace[origin] = 1;
	while(!que.empty()){
		int u = que.top().second;
		que.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		num_rescue[u] += restot[u];
		for(int i = 0; i < vec[u].size(); ++ i){
			int v = vec[u][i].first;
			int w = vec[u][i].second;
			if(dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				num_trace[v] = num_trace[u];
				num_rescue[v] = num_rescue[u];
				que.push(make_pair(-dis[v], v));
			}
			else if(dis[u] + w == dis[v]){
				num_trace[v] += num_trace[u];
				num_rescue[v] = max(num_rescue[u], num_rescue[v]);
			}
		}
	}
	return ;
}
int main(){
	int n, m, st, ed;
	scanf("%d%d%d%d", &n, &m, &st, &ed);
	for(int i = 0; i < n; ++ i)
		scanf("%d", restot + i);
	for(int i = 1; i <= m; ++ i){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		vec[u].push_back(make_pair(v, w));
		vec[v].push_back(make_pair(u, w));
	}
	dijikstra(ed);
	printf("%d %d", num_trace[st], num_rescue[st]);
	return 0;
}

四、我和柳神思路一致，代码实现上稍有不同

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, c1, c2;
int e[510][510], weight[510], dis[510], num[510], w[510];
bool visit[510];
const int inf = 99999999;
int main() {
    scanf("%d%d%d%d", &n, &m, &c1, &c2);
    for(int i = 0; i < n; i++)
        scanf("%d", &weight[i]);
    fill(e[0], e[0] + 510 * 510, inf);
    fill(dis, dis + 510, inf);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        e[a][b] = e[b][a] = c;
    }
    dis[c1] = 0;
    w[c1] = weight[c1];
    num[c1] = 1;
    for(int i = 0; i < n; i++) {
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0; v < n; v++) {
            if(visit[v] == false && e[u][v] != inf) {
                if(dis[u] + e[u][v] < dis[v]) {
                    dis[v] = dis[u] + e[u][v];
                    num[v] = num[u];
                    w[v] = w[u] + weight[v];
                } else if(dis[u] + e[u][v] == dis[v]) {
                    num[v] = num[v] + num[u];
                    if(w[u] + weight[v] > w[v])
                        w[v] = w[u] + weight[v];
                }
            }
        }
    }
    printf("%d %d", num[c2], w[c2]);
    return 0;
}