fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ii;
  4. typedef pair<ii,ii> pi;
  5. vector<pi> g[100001];
  6. typedef vector<pi>::iterator vit;
  7. bool visited[100001];
  8. ii dis[100001];
  9.  
  10. void logic(ii s,ii n)
  11. {
  12.     ii x,y,i;
  13.    for(i=0;i<=100000;i++){
  14.     dis[i]=1000000001;
  15.     visited[i]=false;
  16.    }
  17.     dis[s]=0;
  18.     multiset<pi> m;
  19.     m.insert(make_pair(0,s));
  20.     while(!m.empty())
  21.     {
  22.          pair <ii , ii> p = *m.begin();
  23.          x=p.first; y=p.second;
  24.          m.erase(m.begin());
  25.          if(visited[y])
  26.             continue;
  27.             visited[y]=true;
  28.         for(i=0;i<g[y].size();i++)
  29.         {
  30.             ii e,w;
  31.            e=g[y][i].first;
  32.            w=g[y][i].second;
  33.           if(dis[e]>w+dis[y])
  34.           {
  35.              dis[e]=w+dis[y];
  36.               m.insert(make_pair(dis[e],e));
  37.           }
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     ios_base::sync_with_stdio(0);
  44.     cin.tie(0);
  45.     ii n,m,i,t,j;
  46.     cin>>t;
  47.     while(t--){
  48.   ii k,x,s;
  49.     cin>>n>>k>>x>>m>>s;
  50.     while(m--)
  51.     {
  52.         ii a,b,w;
  53.         cin>>a>>b>>w;
  54.         g[a].push_back(make_pair(b,w));
  55.         g[b].push_back(make_pair(a,w));
  56.  
  57.     }
  58.     for(i=1;i<k;i++)
  59.    {
  60.         for(j=i+1;j<=k;j++)
  61.         {
  62.         g[i].push_back(make_pair(j,x));
  63.         g[j].push_back(make_pair(i,x));
  64.         }
  65.     }
  66.      logic(s,n);
  67.  
  68.     for(i=1;i<=n;i++)
  69.         cout<<dis[i]<<" ";
  70.     cout<<endl;
  71.     }
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0s 18464KB
comments (?)
stdin
copy 
3
5 4 100 2 3
1 5 50
5 3 160
5 4 100 2 3
1 5 50
5 3 140
8 3 15 7 5
3 4 10
4 5 20
5 6 10
6 1 7
3 7 1000
7 8 50
3 5 1000000000
stdout
copy 
100 100 0 100 150 
100 100 0 100 140 
17 32 30 20 0 10 1030 1080
https://ideone.com/tMLTMj
language:
C++ (gcc 8.3)
created:
8 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!