2021 RoboCom 7

RoboCom 7"/>

2021 RoboCom 7

题目：

样例输出：

6 12
1 2 10 5
2 3 16 20
3 1 4 2
2 4 20 22
4 5 2 2
5 3 12 6
4 6 8 5
6 5 10 5
6 1 20 25
1 5 8 5
2 5 2 1
2 6 8 5
4
2 3 6 5

样例输出：

5
5->2
2 1
5->1->3
12 7
5->4->6
10 7
5
0 0

分析：这道题目我们首先要找到一个起点，使得这个起点到其他所有点的最大距离尽可能地小，所以我们只能分别以每个点作为原点跑一遍最短路，这样就可以求出来最佳原点，当然这个过程我们可以直接用floyd来实现，但是需要注意的一点就是floyd三层for循环的遍历顺序，第一层是k，代表的含义就是经过的点的编号是在1~k之间的点所能达到的最短距离，顺序一定不能出错。剩下的就是我们用最佳原点跑一边dijkstra求一下满足题意的最佳路径即可，就是改一下dijkstra更新的条件以及加一个pre数组来记录一下路径。

下面是代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int N=1e3+10;
typedef pair<int,int>PII;
long long f[N][N],w1[N][N],w2[N][N];
long long d[N],w[N],pre[N],st[N],tt;
bool vis[N];
int n,m,k;
void dijkstra(int x)
{priority_queue<PII,vector<PII>,greater<PII> >q;q.push({0,x});memset(d,0x3f,sizeof d);d[x]=0;while(!q.empty()){int begin=q.top().second;q.pop();if(vis[begin]) continue;vis[begin]=true;for(int i=1;i<=n;i++){if(d[i]>d[begin]+w1[begin][i])//代价优先选择小的 {d[i]=d[begin]+w1[begin][i];w[i]=w[begin]+w2[begin][i];pre[i]=begin;q.push({d[i],i});}else if(d[i]==d[begin]+w1[begin][i])//在代价相同时优先选择武器价值高的 {if(w[i]<w[begin]+w2[begin][i]){w[i]=w[begin]+w2[begin][i];pre[i]=begin;q.push({d[i],i});}}}}
}
int main()
{cin>>n>>m;memset(f,0x3f,sizeof f);memset(w1,0x3f,sizeof w1);memset(w2,-0x3f,sizeof w2); for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);scanf("%lld%lld",&w1[u][v],&w2[u][v]);f[v][u]=f[u][v]=w1[v][u]=w1[u][v];w2[v][u]=w2[u][v];}for(int i=1;i<=n;i++) f[i][i]=0;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);long long ans=0x3f3f3f3f3f3f3f3f;int x=0;for(int i=1;i<=n;i++){long long t=0;for(int j=1;j<=n;j++)t=max(t,f[i][j]);if(t<ans)//记录最大距离的最小值 {ans=t;x=i;}}for(int i=1;i<=n;i++) pre[i]=i;dijkstra(x);printf("%d\n",x);int k;cin>>k;while(k--){int t;scanf("%d",&t);tt=0;while(x!=t){st[++tt]=t;t=pre[t];}printf("%d",x);for(int i=tt;i>=1;i--)printf("->%d",st[i]);if(tt)printf("\n%lld %lld\n",d[st[1]],w[st[1]]);elseprintf("\n%lld %lld\n",d[x],w[x]);}return 0;
}