首先题目很长,归纳题意就是一个无向图
其中每条边都有两个权值
距离和价值
题目也问了两个问题:
(1)找一个起点,从这个点出发,到离它最远的点的距离最小:
(2)有多次询问,每次询问一个点,要求输出从起点到这个点距离最小且价值最大的路径。
(1)先用Floyd计算多源最短路,再枚举起点,暴力算出每种情况下的最远距离,取最小值;
(2)Dijkstra算法,按照距离优先,价值其次的原则进行更新。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
struct node
{
int a,b;
}dis[N],g[N][N];
int n,m;
int path[N];
bool vis[N];
void dijkstra(int s)
{
for(int i = 1;i <= n;i ++)
dis[i].a = INF;
dis[s].a = 0;
for(int i = 1;i <= n;i ++)
{
int k,mind = INF;
for(int j = 1;j <= n;j ++)
if(!vis[j] && dis[j].a < mind)
k = j,mind = dis[j].a;
vis[k] = true;
for(int j = 1;j <= n;j ++)
if(dis[k].a + g[k][j].a < dis[j].a || dis[k].a + g[k][j].a == dis[j].a && dis[k].b + g[k][j].b > dis[j].b)
dis[j] = {dis[k].a + g[k][j].a,dis[k].b + g[k][j].b},path[j] = k;
}
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
if(i != j)
g[i][j].a = INF;
while(m --)
{
int x,y,a,b;
scanf("%d %d %d %d",&x,&y,&a,&b);
g[x][y] = g[y][x] = {a,b};
}
for(int k = 1;k <= n;k ++)
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
if(g[i][k].a + g[k][j].a < g[i][j].a)
g[i][j] = {g[i][k].a + g[k][j].a,0};
int s,mind = INF;
for(int i = 1;i <= n;i ++)
{
int maxd = 0;
for(int j = 1;j <= n;j ++)
maxd = max(maxd,g[i][j].a);
if(maxd < mind)
s = i,mind = maxd;
}
dijkstra(s);
cout << s << endl;
int k;
cin >> k;
while(k --)
{
int e;
cin >> e;
int end = e;
stack<int> ans;
while(end != s)
{
ans.push(end);
end = path[end];
}
cout << s;
while(ans.size())
{
printf("->%d",ans.top());
ans.pop();
}
cout << endl << dis[e].a << ' ' << dis[e].b << endl;
}
return 0;
}