tokitsukaze and Event———

tokitsukaze and Event————牛客练习赛50

本文主要是介绍tokitsukaze and Event————牛客练习赛50，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
https://ac.nowcoder.com/acm/contest/1080/D
思路
      题意是给你一个 n 个点 m 条边的无向图，不存在重边和自环，也没有负权边，但是每条边实际上存在两个权值，一个是原状态对应 ai 权值，一个是夜战状态对应 bi 权值，只能在途中某个位置切换形态且只能切换一次，最后到达终点时必须是夜战状态；此外，还增加了一个要求是游戏难度，当难度为 k 时，在1,2,3……,k-1处都不能切换形态，然后给定你起点 s 和终点 t ，让你输出从难度 1 到难度 n 的所有从 s 到 t 的最短路对应的权值和。
      我的想法是建立两个图，两个图唯一的不同是权值不同，一个对应 ai 权值，一个对应 bi 权值，然后分别对两个图求最短路，对于 ai 图以起点 s 为起点求最短路，对于bi图以终点 t 为起点求最短路，（这里采用SPFA求最短路），因为最开始一定是原状态，然后再切换到夜战状态，所以对于 ai 应以起点 s 为起点，对于 bi 应以终点 t 为起点，然后这两个图的最短路径分别存放于 da 和 db 两个数组中，然后从后往前遍历，切换状态对应的最小伤害就是 da[ i ] + db [ i ] ，因为根据前面的两次求最短路径，如果是在 i 处切换状态，那么路径就是 s -> i -> t，而 s -> i对应的最短路径就是da [ i ],i -> t对应的最短路径就是db [ i ]。
      为什么这里采取从后往前遍历，因为一个很显然的结论，难度低的时候对应的最短路一定小于等于难度高的时候，那么比较过程肯定是拿上一个较高难度对应的值和当前的难度对应值相比较，否则难度从低到高的话，最后输出全是最低值，因为最短路径我们肯定是用min函数的。

c++代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N=1e5+5;
const int INF=1e9+10;struct Graph
{vector<int> w;vector<int> edge;
}Ga[N],Gb[N];ll da[N],db[N],vis_a[N],vis_b[N],ans[N];
int n,m;void add(ll u,ll v,ll a,ll b)
{Ga[u].edge.push_back(v);Ga[u].w.push_back(a);Gb[u].edge.push_back(v);Gb[u].w.push_back(b);}void init()
{memset(da,INF,sizeof(da));memset(db,INF,sizeof(db));memset(vis_a,0,sizeof(vis_a));memset(vis_b,0,sizeof(vis_b));memset(ans,INF,sizeof(ans));
}int main()
{scanf("%d%d",&n,&m);for(int i=0;i<m;i++){ll u,v,a,b;scanf("%lld%lld%lld%lld",&u,&v,&a,&b);add(u,v,a,b);add(v,u,a,b);}init();ll s,t;scanf("%lld%lld",&s,&t);vis_a[s]=1;da[s]=0;queue<int> q1;q1.push(s);while(q1.size()){auto x=q1.front();q1.pop();vis_a[x]=0;for(int i=0;i<Ga[x].edge.size();i++){int j=Ga[x].edge[i];if(da[j]>da[x]+Ga[x].w[i]){da[j]=da[x]+Ga[x].w[i];if(!vis_a[j]){q1.push(j);vis_a[j]=1;}}}}vis_b[t]=1;db[t]=0;queue<int> q2;q2.push(t);while(q2.size()){auto x=q2.front();q2.pop();vis_b[x]=0;for(int i=0;i<Gb[x].edge.size();i++){int j=Gb[x].edge[i];if(db[j]>db[x]+Gb[x].w[i]){db[j]=db[x]+Gb[x].w[i];if(!vis_b[j]){q2.push(j);vis_b[j]=1;}}}}for(int i=n;i>=0;i--){ans[i]=min(ans[i+1],da[i]+db[i]);}for(int i=1;i<=n;i++){printf("%lld\n",ans[i]);}return 0;
}