很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 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;
}