本文主要是介绍【JZOJ4597】现世斩，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
异变又发生了，魂魄妖梦作为幻想乡的一名自(cheng)机(guan)，主动前去解决异变。
我们用一个n个点、m条边的无向联通图来表示妖梦可选择的路线，妖梦从白玉楼出发，白玉楼被视为编号为1的点，编号为2——n的点是幻想乡的村庄，其中编号为n的村庄发生了异变。
每条边上可能会有一些妖怪袭击人类（然而妖梦是半人半灵），所以对于第i条边，妖梦需要t[i]分钟通过这条路。妖梦带了她的人符[现世斩]，可以使所有连接点x的边的通过时间变成1（x可以任意指定）。然而为了保留足够的力量解决异变，妖梦只会用这个符卡一次。妖梦想知道，她到达村庄n的最短时间是多少。
Solution
显然把原图分成三层，跑一次最短路即可。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define N 300001
#define M 4000001
#define ll long long
using namespace std;
int to[M],next[M],last[M],val[M],num=0;
void link(int x,int y,int c)
{num++;to[num]=y;next[num]=last[x];last[x]=num;val[num]=c;
}
int d[M];
ll dis[N];
bool vis[N];
void spfa(int s)
{memset(dis,60,sizeof(dis));dis[1]=0;vis[1]=true;d[1]=1;int l=0,r=1;while(l<r){int x=d[++l];for(int i=last[x];i;i=next[i]){int v=to[i];if(dis[x]+val[i]<dis[v]){dis[v]=dis[x]+val[i];if(!vis[v]){vis[v]=true;d[++r]=v;}}}vis[x]=false;}
}
int main()
{freopen("cut.in","r",stdin);freopen("cut.out","w",stdout);int n,m;cin>>n>>m;fo(i,1,m){ int u,v,w;scanf("%d %d %d",&u,&v,&w);if(u!=v){link(u,v,w);link(v,u,w);link(u,v+n,1);link(u+n,v+n*2,1);link(v,u+n,1);link(v+n,u+n*2,1);link(u+n*2,v+n*2,w);link(v+n*2,u+n*2,w);}}spfa(1);cout<<dis[n*3];
}这篇关于【JZOJ4597】现世斩的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
