2021 RoboCom 世界机器人开发者大赛

开发者大赛"/>

2021 RoboCom 世界机器人开发者大赛

很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。

你的任务有两件：

帮助玩家确定一个最合算的空降位置，即空降到地图中的某个堡垒，使得玩家从这个空降点出发，到攻下最难攻克（即耗费能量最多）的那个堡垒所需要的能量最小；
从这个空降点出发，帮助玩家找到攻克任意一个其想要攻克的堡垒的最省能量的路径。如果这种路径不唯一，则选择沿途缴获武器总价值最高的解，题目保证这种解是唯一的。
输入格式:
输入第一行给出两个正整数 N (≤1000) 和 M，其中 N 是堡垒总数，M 是怪兽总数。为简单起见，我们将堡垒从 1 到 N 编号。随后 M 行，第 i 行给出了第 i 只怪兽的信息，格式如下：

B1 B2 怪兽能量 武器价值
其中 B1 和 B2 是怪兽把守的道路两端的堡垒编号。题目保证每对堡垒之间只有一只怪兽把守，并且 怪兽能量 和 武器价值 都是不超过 100 的正整数。

再后面是一个正整数 K（≤N）和玩家想要攻克的 K 个目标堡垒的编号。

输出格式:
首先在一行中输出玩家空降的堡垒编号 B0。如果有多种可能，则输出编号最小的那个。

随后依次为玩家想要攻克的每个堡垒 B 推荐最省能量的攻克路径，并列出需要耗费的能量值和沿途缴获武器的总价值。注意如果最省力的路径不唯一，则选择沿途缴获武器总价值最高的解。格式为：

B0->途经堡垒1->…->B
总耗费能量 武器总价值
输入样例:
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
添加链接描述

朴素版dijkstra勉强卡时AC

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+9;
int arr[N][N],reven[N][N];
int dist[N],vis[N];
int n,m;
int path[N],ans[N],tot[N],sum[N];
int dij(int s,int d){memset(path,0,sizeof path);memset(vis,0,sizeof vis);memset(dist,0x3f,sizeof dist);memset(tot,0,sizeof tot);dist[s]=0;int k;for(int i=1;i<=n;i++){int tmp=1e9;for(int j=1;j<=n;j++){if(!vis[j]&&tmp>dist[j]){tmp=dist[j],k=j;}}if(tmp==1e9)break;//cout<<"---"<<k<<" "<<dist[k]<<endl;vis[k]=1;for(int j=1;j<=n;j++){if(!vis[j]&&dist[j]>dist[k]+arr[k][j]){dist[j]=dist[k]+arr[k][j];path[j]=k;tot[j]=tot[k]+reven[k][j];}else if(!vis[j]&&dist[j]==dist[k]+arr[k][j]){if(tot[k]+reven[j][k]>tot[j]){tot[j]=tot[k]+reven[k][j];path[j]=k;}}}}return dist[d];
}
int main(){scanf("%d%d",&n,&m);memset(arr,0x3f,sizeof arr);for(int i=1;i<=m;i++){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);arr[a][b]=arr[b][a]=c;reven[a][b]=reven[b][a]=d;}int p=0x3f3f3f3f,res;for(int i=1;i<=n;i++){int mi=0;dij(i,n);for(int j=1;j<=n;j++){//cout<<i<<" "<<j<<" "<<dij(i,j)<<endl;if(i!=j){mi=max(mi,dist[j]);}}//cout<<i<<" "<<mi<<endl;if(mi<p&&mi!=0){p=mi;res=i;}}cout<<res<<endl;//cout<<p<<endl;int k;scanf("%d",&k);dij(res,n);for(int i=1;i<=k;i++){int a,cur=0;scanf("%d",&a);if(a==res)printf("%d\n0 0\n",res);else {for(int j=a;j>=0;j=path[j]){ans[++cur]=j;if(j==res)break;}//cout<<cur<<endl;for(int j=cur;j>1;--j){printf("%d->",ans[j]);}printf("%d\n",a);printf("%d %d\n",dist[a],tot[a]);}}return 0;
}

不知道为什么写的链式前向星加堆优化dijkstra反而会tle

#include<bits/stdc++.h>
using namespace std;
const int N=1009,M=1e7+9;
int n,m;
int e[M],ne[M],w1[M],w2[M],h[N],idx;
void add(int a,int b,int c,int d){w1[idx]=c,w2[idx]=d;e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
typedef pair<int ,int> pii;
int dist_1[N],dist_2[N];
int vis[N],path[N];
void dijkstra(int s){priority_queue<pii,vector<pii>,greater<pii>> q;for(int i=1;i<=1000;i++){dist_2[i]=path[i]=vis[i]=0;dist_1[i]=0x3f3f3f3f;}dist_1[s]=0;q.push({0,s});while(q.size()){int x=q.top().second;q.pop();if(vis[x])continue;vis[x]=1;for(int i=h[x];~i;i=ne[i]){int j=e[i],c=w1[i],d=w2[i];if(dist_1[j]>dist_1[x]+c){dist_1[j]=dist_1[x]+c;path[j]=x;dist_2[j]=dist_2[x]+d;q.push({dist_1[j],j});}else if(dist_1[j]==dist_1[x]+c){if(dist_2[x]+d>dist_2[j]){dist_2[j]=dist_2[x]+d;path[j]=x;}}}}}
int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);for(int i=1;i<=m;i++){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);add(a,b,c,d);add(b,a,c,d);}int res,mx=0x3f3f3f3f;for(int i=1;i<=n;i++){int p=0;dijkstra(i);for(int j=1;j<=n;j++){p=max(p,dist_1[j]);// cout<<dist_1[j]<<endl;}if(p<mx){mx=p;res=i;}}cout<<res<<endl;int k=0;scanf("%d",&k);dijkstra(res);int ans[N];for(int i=1;i<=k;i++){int x,tot=0;scanf("%d",&x);if(x==res)printf("%d\n0 0\n",res);else {for(int j=x;j>=0;j=path[j]){ans[++tot]=j;if(j==res)break;}for(int j=tot;j>1;j--){printf("%d->",ans[j]);}printf("%d\n%d %d\n",x,dist_1[x],dist_2[x]);}}return 0;
}