admin管理员组文章数量:1577827
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;
}
版权声明:本文标题:1003 Emergency (25 分)(测试点2,3,4) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1727822923a1131937.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论