输入样例
6 121 2 10 52 3 16 203 1 4 22 4 20 224 5 2 25 3 12 64 6 8 56 5 10 56 1 20 251 5 8 52 5 2 12 6 8 542 3 6 5
输出样例
55->22 15->1->312 75->4->610 750 0
递归为什么总写爆
#include <bits/stdc++.h>using namespace std;#define inf 0x3f3f3f3f#define pii pair<int,int>const int N=1005;struct edge{int to,nex,w1,w2;}e[N*N];int head[N];int cnt;void add(int u,int v,int w1,int w2){e[++cnt].w1=w1;e[cnt].w2=w2;e[cnt].to=v;e[cnt].nex=head[u];head[u]=cnt;}int n,m,k;int vis[N];int dist[N];int maxV[N];//最短路径+最大价值 int pre[N];int dijikstra(int s){//从s出发的单元最短路径 for(int i=1;i<=n;i++){dist[i]=inf;vis[i]=false;maxV[i]=0;} dist[s]=0;priority_queue<pii,vector<pii>,greater<pii> > Q;Q.push({0,s});for(int t=0;t<n;t++){if(Q.empty())break;pii p=Q.top();Q.pop();int v=p.second;if(vis[v]){t--;continue;}vis[v]=1;for(int i=head[v];i;i=e[i].nex){int w=e[i].w1;int to=e[i].to;if(!vis[to]&&dist[to]>dist[v]+w){dist[to]=dist[v]+w;maxV[to]=maxV[v]+e[i].w2;pre[to]=v; Q.push({dist[to],to});}else if(!vis[to]&&dist[to]==dist[v]+w){if(maxV[to]<maxV[v]+e[i].w2){maxV[to]=maxV[v]+e[i].w2;pre[to]=v;Q.push({dist[to],to});}}}}//for(int i=1;i<=n;i++){//cout<<dist[i]<<" ";//}//cout<<endl;int ms=0;//到别的点的最短距离的最大值for(int i=1;i<=n;i++){if(dist[i]>ms){ms=dist[i];}} return ms;}int a[N];//找空降点i，保存i到别点最短路径的最大值，看谁的最大值最小 int b[N];//保存要访问的城堡 void dfs(int u,int v){//输出u到v的路径 //if(u!=v){//dfs(u,pre[v]);//cout<<u<<"->";//}//else {//cout<<u<<endl;//return ;//}if(u==v)return;dfs(u,pre[v]);cout<<"->"<<v;}signed main(){//首先找到空降的点，该点g要满足//g到别的所有点的最短距离的最大距离最小 //再找空降点到b[]中的最短距离和路径 //注意这里的标准是 w1尽可能小，w1相等时w要尽可能大 cin>>n>>m;int u,v,w1,w2;for(int i=0;i<m;i++){cin>>u>>v>>w1>>w2;add(u,v,w1,w2);add(v,u,w1,w2);}cin>>k;for(int i=0;i<k;i++)cin>>b[i];for(int i=1;i<=n;i++){a[i]=dijikstra(i);} int id=1;for(int i=2;i<=n;i++){if(a[id]>a[i]){id=i;}}cout<<id<<endl;//空降点dijikstra(id);for(int i=0;i<k;i++){//输出路径，最小能量，最大武器价值 cout<<id;dfs(id,b[i]);cout<<endl;cout<<dist[b[i]]<<" "<<maxV[b[i]]<<endl; } return 0;}
如果觉得《7-3 打怪升级》对你有帮助，请点赞、收藏，并留下你的观点哦！
