admin管理员组文章数量:1577818
题目链接:
1003 Emergency
题意:
给定一张图,且每个节点有一个权值,给定起点和终点,求起点和终点之间最短路径的条数和权值和最大值。
思路:
对dijkstra算法进行一定变形即可。用tot[i]表示起点到第i个点最短路径的条数。num[i]表示起点到第i个点的最短路中权值和的最大值,dis[i]表示当前从起点到i的最短路的距离。因此只需在最后的更新操作中进行适当修改:
当dis[j] == dis[pos]+mp[pos][j]时:
tot[j]+=tot[pos]; num[j]=max(num[j],num[pos]+val[j]);
当dis[j] > dis[pos]+mp[pos][j]时:
tot[j]=tot[pos]; num[j]=num[pos]+val[j]; dis[j]=dis[pos]+mp[pos][j];
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1024 + 10;
const int inf = 1e9 + 7;
int n, m, st, ed;
int val[MAX];
int mp[MAX][MAX];
int dis[MAX], num[MAX], tot[MAX], vis[MAX];
void dijkstra(int x)
{
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) tot[i] = 0;
tot[x] = 1;
for (int i = 0; i < n; i++) dis[i] = inf;
dis[x] = 0;
for (int i = 0; i < n; i++) {
int minn = inf;
int pos = -1;
for (int j = 0; j < n; j++) {
if (vis[j] == 0 && dis[j] < minn) {
minn = dis[j];
pos = j;
}
}
vis[pos] = 1;
for (int j = 0; j < n; j++) {
if (j == pos) continue;
if (dis[pos] + mp[pos][j] == dis[j]) {
tot[j] += tot[pos];
num[j] = max(num[j], num[pos] + val[j]);
}
else if (dis[pos] + mp[pos][j] < dis[j]) {
tot[j] = tot[pos];
num[j] = num[pos] + val[j];
dis[j] = dis[pos] + mp[pos][j];
}
}
}
return;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &st, &ed);
for (int i = 0; i < n; i++) {
scanf("%d", &val[i]);
num[i] = val[i];
}
//初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mp[i][j] = inf;
}
}
for (int i = 0; i < m; i++) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
mp[x][y] = mp[y][x] = v;
}
for (int i = 0; i < n; i++) mp[i][i] = 0;
dijkstra(st);
printf("%d %d\n", tot[ed], num[ed]);
return 0;
}
版权声明:本文标题:1003 Emergency(两点间最短路径的条数) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1727823718a1132023.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论