CodeForces845G-Shortest PathProblem?
2614 단어 SPFA최단로 문제CodeForces
Note that graph can contain multiple edges and loops. It is guaranteed that the graph is connected.Input
The first line contains two numbers n and m (1 ≤ n ≤ 100000, n - 1 ≤ m ≤ 100000) — the number of vertices and the number of edges, respectively.
Then m lines follow, each line containing three integer numbers x, y and w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108). These numbers denote an edge that connects vertices x and y and has weight w.Output
Print one number — the minimum length of path between vertices 1 and n.Examples
Input
3 3
1 2 3
1 3 2
3 2 0
Output
2
Input
2 2
1 1 3
1 2 3
Output
0
이것은 지점 1에서 지점 N으로 가는 길의 이단과 최단로를 구하는 문제이다.하나의 고리와 우리는 모두 그 고리를 0으로 만들 수 있다(한 고리가 두 번 지나면 0 또는 0이다). 한 고리는 한 번 걷거나 가지 않는다.우리는 1에서 N까지의 길을 마음대로 찾을 수 있다. 그리고 다른 고리나 모든 고리를 찾아 최소치를 찾으면 된다.
AC 코드는 다음과 같습니다.
#includeusing namespace std;const int maxn=1e5+10;const int INF=0x3f3f3f3f;typedef long long LL;int n,m,u,v,w,tot,temp,first[maxn],vis[maxn],a[maxn],b[maxn],dis[maxn];struct Edge{ int to,w,net;} edge[maxn<<1];inline void Init(){ memset(first,-1,sizeof first); memset(vis,0,sizeof vis); memset(b,0,sizeof b); tot=1;temp=0;}inline void addedge(int u,int v,int w){ edge[tot].to=v; edge[tot].w =w; edge[tot].net=first[u]; first[u]=tot++;}inline void dfs(int id,int len){ vis[id]=1; dis[id]=len; for(int i=first[id];~i;i=edge[i].net) { if(vis[edge[i].to]) a[++temp]=dis[edge[i].to]^edge[i].w^len; else dfs(edge[i].to,len^edge[i].w); }}inline void Guass(){ for(int i=1;i<=temp;i++) { for(int j=31;j>=0;j--) { if((a[i] >> j) & 1) { if(!b[j]) { b[j]=a[i]; break; } else a[i]^=b[j]; } } }}int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; Init(); for(int i=1;i<=m;i++) { cin>>u>>v>>w; addedge(u,v,w); addedge(v,u,w); } dfs(1,0); int ans=dis[n]; for(int i=31;i>=0;i--) ans=min(ans,ans^b[i]); cout< return 0;}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU4276 The Ghost Blows Light SPFA & 트리 dp제목의 소개와 사고방식은 아래의 블로그를 완전히 참고하였다.http://blog.csdn.net/acm_cxlove/article/details/7964739 이 문제를 푸는 것은 주로 SPFA 코드에 대한 자신의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.