7-3 single source shortest circuit for strange play upgrade

7-3 Have to upgrade
fraction 25
author Chen Yue
Company Zhejiang University
dgsj.JPG

Many games have a strange upgrade link , Players need to defeat a series of monsters to win achievements and badges . Here we consider a simple upgrade game , The rule of the game is , Given that there is N A map of a fortress , There are roads between the forts , Every road is guarded by a monster . The monster itself has energy , The weapon in hand is valuable . The energy needed to defeat the monster is equal to the energy of the monster itself , And once the monster is defeated , The weapon belongs to the player —— Of course, the more valuable the weapons seized , The happier the players are .

You have two tasks ：

Help players determine the most cost-effective airborne position , Parachute into a fortress , Make players start from this airborne point , To capture the most difficult （ That is, it consumes the most energy ） The fortress that needs the least energy ;
From this airborne point , Help players find the most energy-saving way to conquer any fortress they want to conquer . If this path is not unique , Then choose the solution with the highest total value of weapons seized along the way , The problem guarantees that this solution is unique .
Input format :
The first line of input gives two positive integers N (≤1000) and M, among N Is the total number of fortresses ,M Is the total number of monsters . For the sake of simplicity , We took the fort from 1 To N Number . And then M That's ok , The first i Line gives the second line i Information about a monster , The format is as follows ：

B1 B2 Monster Energy The value of weapons
among B1 and B2 It's the fortress number at both ends of the monster guarded road . The problem is to ensure that there is only one monster guarding between each pair of forts , also Monster Energy and The value of weapons No more than 100 The positive integer .

Followed by a positive integer K（≤N） Players who want to conquer K The number of the target fortress .

Output format :
First, output the fortress number of the player airborne in one line B0. If there are many possibilities , Then output the one with the smallest number .

Then each fortress that the player wants to conquer B Recommend the most energy-saving attack path , And list the energy required and the total value of weapons captured along the way . Note that if the most labor-saving path is not unique , Then choose the solution with the highest total value of weapons seized along the way . The format is ：

B0-> Passing fortress 1->…->B
Total energy consumption The total value of weapons
sample input :
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
sample output :
5
5->2
2 1
5->1->3
12 7
5->4->6
10 7
5
0 0

Adjacency matrix forgot to initialize , Debug 2 Hours 🤮🤮🤮

#include<bits/stdc++.h>

using namespace std;
const int N=1004,INF=0x3f3f3f3f;
int g[N][N],vv[N][N];
int dist[N],s[N],f[N];
bool st[N];
int n,m;

void djs(int u){
    
	memset(dist,0x3f,sizeof dist);
	memset(st,0,sizeof st);
	memset(s,0,sizeof s);
	memset(f,0,sizeof f);
	dist[u]=0;
	s[u]=0;
	f[u]=u;
	for(int i=1;i<=n;++i)
	{
    
		int t=-1;
		for(int j=1;j<=n;++j)
		{
    
			if(st[j]==false&&(t==-1||dist[j]<dist[t]))t=j;
		}
		st[t]=true;
		for(int j=1;j<=n;++j){
    
			if(dist[j]>dist[t]+g[t][j]){
    
				dist[j]=dist[t]+g[t][j];
				s[j]=s[t]+vv[t][j];
				f[j]=t;
			}else if(dist[j]==dist[t]+g[t][j]){
    
				if(s[j]<s[t]+vv[t][j]){
    
					s[j]=s[t]+vv[t][j];
					f[j]=t;
				}
			}
		}
	}
}

void dfs(int x,int &s)
{
    
	if(f[x]==x){
    
		cout<<x;return;
	}
	else {
    
		s+=vv[x][f[x]];
		//cout<<f[x];
		//if(f[f[x]]==x)cout<<"NO";
		dfs(f[x],s);
		cout<<"->"<<x;
	}
}
int main(){
    
    memset(g,0x3f,sizeof g);
	cin>>n>>m;
	while(m--)
	{
    
		int x,y,w,v;
		cin>>x>>y>>w>>v;
		g[x][y]=g[y][x]=w;
		vv[x][y]=vv[y][x]=v;
	}
	int u=1,len=INF;
	for(int i=1;i<=n;++i)
	{
    
		djs(i);
		int ma=0;
		for(int j=1;j<=n;++j){
    
			ma=max(ma,dist[j]);
		}
		if(ma<len){
    
			len=ma;
			u=i;
		}
	}
	cout<<u<<endl;
	int k;cin>>k;

	djs(u);
	while(k--){
    
		int x;cin>>x;
		int ss=0;
		dfs(x,ss);
		cout<<endl;
		cout<<dist[x]<<" "<<s[x]<<endl;
	}
	return 0;
}