fork download 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. const long long oo=1e18;
  6. const int mod=1e9+7;
  7. void home()
  8. {
  9.     freopen("main.inp","r",stdin);
  10.     freopen("main.out","w",stdout);
  11. }
  12. bool bit(int x,int i){return (x>>i)&1;}
  13. int n,m,node;
  14. vector<pair<int,int>>a[600005];
  15. vector<pair<int,int>>g[600005];
  16. map<pair<int,int>,int>mp;
  17. long long d[600005];
  18. long long DIJK()
  19. {
  20.     fill(d+1,d+node+1,oo);
  21.     priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
  22.     q.push({0,1});d[1]=0;
  23.     while(!q.empty())
  24.     {
  25.         auto [w,u]=q.top();q.pop();
  26.         if(d[u]<w)continue;
  27.         for(auto [w1,v]:g[u])
  28.         {
  29.             if(d[v]>d[u]+w1)
  30.             {
  31.                 d[v]=d[u]+w1;
  32.                 q.push({d[v],v});
  33.             }
  34.         }
  35.     }
  36.     return d[n];
  37. }
  38. void Tcmduc_VOI26()
  39. {
  40.     cin>>n>>m;node=n;
  41.     for(int i=1;i<=m;i++)
  42.     {
  43.         int u,v,w;cin>>u>>v>>w;
  44.         a[u].push_back({w,v});
  45.         a[v].push_back({w,u});
  46.         mp[{u,v}]=++node;
  47.         mp[{v,u}]=node;
  48.     }
  49.     for(int u=1;u<=n;u++)
  50.     {
  51.         sort(a[u].begin(),a[u].end());int pre=0,we=0;
  52.         for(auto [w,v]:a[u])
  53.         {
  54.             int x=mp[{u,v}];
  55.             if(pre)
  56.             {
  57.                 g[pre].push_back({w-we,x});
  58.                 g[x].push_back({w-we,pre});
  59.             }
  60.             pre=x;we=w;
  61.         }
  62.     }
  63.     for(auto [w,v]:a[1])
  64.     {
  65.         int x=mp[{1,v}];
  66.         g[1].push_back({w,x});
  67.         g[x].push_back({w,1});
  68.     }
  69.     for(auto [w,v]:a[n])
  70.     {
  71.         int x=mp[{n,v}];
  72.         g[n].push_back({0,x});
  73.         g[x].push_back({0,n});
  74.     }
  75.     cout<<DIJK()<<'\n';
  76. }
  77. int main()
  78. {
  79.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);//home();
  80.     Tcmduc_VOI26();
  81.     cerr<<'\n';
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout #stderr 0.01s 33132KB
comments (?)
stdin 
Standard input is empty
stdout 
0
stderr 

    

	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			


			                        
			
			

				

	
					
					 https://ideone.com/sXi5Bz
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
9 days ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!