Robocom2021 初赛

怼烎@ 2024-03-17 19:16 8阅读 0赞

收录一下Robocom初赛的屌题，调了我一个多小时，是我菜了

[题目详情 - 7-3 打怪升级 (pintia.cn)][- 7-3 _ _pintia.cn]

题意：

![f8a8e98b40a046a186afac80737453d9.png][]

![7b95232883b4427d9d245d28cd4fc9e0.png][]

![1048f164de6c467c9ea9230502b4920f.png][]

Code：

#include<bits/stdc++.h> 
    using namespace std;
     
    int n, m, a, b, c, d, q, p;
    int f[1005][1005];
     
    const int N = 2000000;
    int ne[N], w[N], ww[N], e[N], h[N], idx, dist[1005];
    bool st[1005];
     
    struct node{
    	int distance, power, name;
    };
     
    struct cmp{
    	bool operator() (node x, node y){
    		if(x.distance != y.distance) return x.distance > y.distance;
    		else{
    			if(x.power != y.power) return x.power < y.power;
    			else return x.name < y.name;
    		} 
    	}
    }; 
     
    int pre[1005];//难点1
    int pw[1005];//难点2 
     
    void add(int a, int b, int c, int d){
    	e[idx] = b, w[idx] = c, ww[idx] = d, ne[idx] = h[a], h[a] = idx++;
    }
     
    void dijk(int s){
    	priority_queue<node, vector<node>, cmp> heap;
    	heap.push({0, 0, s});
    	dist[s] = 0;
    	while(heap.size()){
    		node head = heap.top();
    		heap.pop();
    		int ver = head.name, distance = head.distance, power = head.power;
    		if(st[ver]) continue;
    		st[ver] = 1;
    		
    		for(int i = h[ver]; i!=-1; i = ne[i]){
    			int j = e[i];
    			if(distance + w[i] < dist[j]){
    				pre[j] = ver;
    				dist[j] = distance + w[i];
    				pw[j] = power + ww[i];
    				heap.push({dist[j], pw[j], j});
    			}
    			else if(distance + w[i] == dist[j]){
    				if(power + ww[i] > pw[j]){
    					pre[j] = ver;
    					dist[j] = distance + w[i];
    					pw[j] = power + ww[i];
    					heap.push({dist[j], pw[j], j});
    				}
    			}
    		}
    	}
    //	cout<<"debug";
    }
     
    int main(){
    	memset(h, -1, sizeof h);
    	memset(dist, 127, sizeof dist);
    	
    	cin>>n>>m;
    	memset(f, 63, sizeof f);
    	for(int i = 1; i<=m; ++i){
    		cin>>a>>b>>c>>d;
    		f[a][b] = c;
    		f[b][a] = c;
    		add(a,b,c,d);
    		add(b,a,c,d);
    	}
     
    	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]);
     
    	int ans1 = 0;
    	int ans1max = 100000000;
    	for(int i = 1; i<=n; ++i){
    		int curmax = 0;
    		for(int j = 1; j<=n; ++j){
    			curmax = max(curmax, f[i][j]);
    		}
    		if(curmax<ans1max){
    			ans1 = i;
    			ans1max = curmax;
    		}
    	}
    	cout<<ans1<<endl;
     
    	dijk(ans1);
    	cin>>q;
    	for(int i = 1; i<=q; ++i){
    		cin>>p;
    		vector<int> ans2;
    		
    		int cur = p;
    		while(cur!=ans1){
    			ans2.push_back(cur);
    			cur = pre[cur];
    		}
    		ans2.push_back(ans1);
    		
    		for(int i = ans2.size()-1; i>=0; --i){
    			cout<<ans2[i];
    			if(i!=0) cout<<"->";
    		}
    		cout<<"\n";		
    		
    		cout<<dist[p]<<" "<<pw[p]<<endl;
    	}
     
        return 0;
    }

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=2e6+10;
    const int mxe=2e6+10;
    const int Inf=0x3f3f3f3f;
    const int mod=998244353;
    
    struct ty{
    	int to,next,w1,w2;
    }edge[mxe<<1];
    
    struct ty2{
    	//能量，价值
    	int x,dist1,dist2;
    };
    
    struct cmp{
    	bool operator()(ty2 x,ty2 y){
    		if(x.dist1!=y.dist1) return x.dist1<y.dist1;
    		else{
    			if(x.dist2!=y.dist2) return x.dist2<y.dist2;
    			else return x.x<y.x;
    		}
    	}
    };
    
    priority_queue<ty2,vector<ty2>,cmp> Q;
    
    int N,M,K,tot=0,u,v,w1,w2,ansmi,x;
    int head[mxn];
    int dis[1005][1005],vis[mxn];
    int dis1[mxn],pw[mxn];
    int pre[mxn];
    
    void add(int u,int v,int w1,int w2){
    	edge[tot].w1=w1;
    	edge[tot].w2=w2;
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=N;i++){
    		head[i]=-1;
    	}
    }
    void Floyd(){
    	for(int k=1;k<=N;k++){
    		for(int i=1;i<=N;i++){
    			for(int j=1;j<=N;j++){
    				if(i==j||i==k||k==j) continue;
    				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    			}
    		}
    	}
    	int mi=Inf;
    	for(int i=1;i<=N;i++){
    		int mx=-1;
    		for(int j=1;j<=N;j++){
    			mx=max(mx,dis[i][j]);
    		}
    		if(mi>mx){
    			mi=mx;
    			ansmi=i;
    		}
    	}
    }
    void dij(int s){
    	//能量，价值
    	memset(dis1,0x3f,sizeof(dis1));
    	memset(vis,0,sizeof(vis));
    	dis1[s]=0;
    	Q.push({s,0,0});
    	while(!Q.empty()){
    		auto u=Q.top();
    		Q.pop();
    		if(vis[u.x]) continue;
    		vis[u.x]=1;
    		for(int i=head[u.x];~i;i=edge[i].next){
    			if(dis1[edge[i].to]>u.dist1+edge[i].w1){
    				dis1[edge[i].to]=u.dist1+edge[i].w1;
    				pre[edge[i].to]=u.x;
    				pw[edge[i].to]=u.dist2+edge[i].w2;
    				Q.push({edge[i].to,dis1[edge[i].to],pw[edge[i].to]});
    			}else if(dis1[edge[i].to]==u.dist1+edge[i].w1){
    				if(pw[edge[i].to]<u.dist2+edge[i].w2){
    					pre[edge[i].to]=u.x;
    					dis1[edge[i].to]=u.dist1+edge[i].w1;
    					pw[edge[i].to]=u.dist2+edge[i].w2;
    					Q.push({edge[i].to,dis1[edge[i].to],pw[edge[i].to]});
    				}
    			}
    		}
    	}
    }
    void solve(){
    	cin>>N>>M;
    	G_init();
    	for(int i=1;i<=N;i++){
    		for(int j=1;j<=M;j++){
    			if(i==j) dis[i][j]=0;
    			else dis[i][j]=Inf;
    		}
    	}
    	for(int i=1;i<=M;i++){
    		cin>>u>>v>>w1>>w2;
    		dis[u][v]=dis[v][u]=w1;
    		add(u,v,w1,w2);
    		add(v,u,w1,w2);
    	}
    	Floyd();
    	cout<<ansmi<<'\n';
    	dij(ansmi);
    	cin>>K;
    	for(int i=1;i<=K;i++){
    		cin>>x;
    		vector<int> ans;
    		int cur=x;
    		while(cur!=ansmi){
    			ans.push_back(cur);
    			cur=pre[cur];
    		}
    		ans.push_back(ansmi);
    		for(int i=ans.size()-1;i>=0;i--){
    			cout<<ans[i];
    			if(i!=0) cout<<"->";
    		}
    		cout<<'\n';
    		cout<<dis1[x]<<" "<<pw[x]<<'\n';
    	}
    }
    signed main(){
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[- 7-3 _ _pintia.cn]: https://pintia.cn/problem-sets/1446838676759703552/exam/problems/1446838732288094210
[f8a8e98b40a046a186afac80737453d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/39bb391a0d0b49a8a6feef17a1aeb59d.png
[7b95232883b4427d9d245d28cd4fc9e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f4a46f6946194609abcfef1b1a957232.png
[1048f164de6c467c9ea9230502b4920f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7dbc3903d9274f8a9cda6159adbed34c.png