fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int max(int x,int y){
  6. 	if(x>y){
  7. 		return x;
  8. 	}
  9. 	return y;
  10. }
  11.  
  12.  
  13. void dijkstra(vector<int> v[],int n,unordered_map<int,int> &mp){
  14.     bool vis[n+1];
  15.     int dist[n+1];
  16.     memset(vis,false,sizeof(vis));
  17.     memset(dist,1000000000,sizeof(dist));
  18.     dist[1] = 0;
  19.     multiset<pair<int,pair<int,int>>> s;
  20.  
  21.     s.insert({0,{0,1}});
  22.  
  23.     while(!s.empty()){
  24.  
  25.         pair <int , pair<int,int>> p = *s.begin();
  26.         s.erase(s.begin());
  27.  
  28.         int x = p.second.second; int wei = p.first;
  29.         cout<<x<<" "<<wei<<" "<<dist[x]<<'\n';
  30.         if( vis[x] ) continue;
  31.         vis[x] = true;
  32.  
  33.         for(int i = 0; i < v[x].size(); i++){
  34.             int e = v[x][i];
  35.             cout<<dist[e]<<'\n';
  36.             if(dist[x] + 1 < dist[e]  ){
  37.                 dist[e] = dist[x] + 1;
  38.                 int prio;
  39.                 if(mp.find(e)==mp.end()){
  40.                     prio=1;
  41.                 }
  42.                 else{
  43.                     prio=2;
  44.                 }
  45.                 s.insert({dist[e],  {prio,e}} );
  46.             }
  47.         }
  48.     }
  49.  
  50.     cout<<dist[n];
  51.  
  52. }
  53.  
  54. signed main(){
  55.  
  56. 	int n,m,k;
  57. 	cin>>n>>m>>k;
  58.  
  59. 	vector<int> sp(k);
  60. 	unordered_map<int,int> mp;
  61. 	for(int i=0;i<k;++i){
  62. 		cin>>sp[i];
  63. 		mp[sp[i]]=1;
  64. 	}
  65.  
  66. 	vector<int> g[n+1];
  67. 	for(int i=0;i<m;++i){
  68. 		int u,v;
  69. 		cin>>u>>v;
  70. 		g[u].push_back(v);
  71. 		g[v].push_back(u);
  72. 	}
  73.  
  74. 	dijkstra(g,n,mp);
  75.  
  76. }
Success #stdin #stdout 0s 4540KB
comments (?)
stdin
copy 
5 5 3
1 3 5
1 2
2 3
3 4
3 5
2 4
stdout
copy 
1 0 0
0
0
https://ideone.com/EL8WS5
language:
C++ (gcc 8.3)
created:
4 years 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!