fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     #define pb push_back
  3.     #define mp make_pair
  4.     #define ll long long
  5.     #define MOD 1e9 + 7
  6.     #define ull unsigned long long
  7.     #define iloop(a,b) for(ll i = a; i < b; ++i)
  8.     #define jloop(a,b) for(ll j = a; j < b; ++j)
  9.     using namespace std;
  10.     typedef vector<int> vi; 
  11.     typedef vector<vi> vvi; 
  12.     typedef pair<int,int> ii; 
  13.     #define sz(a) int((a).size()) 
  14.     #define pb push_back 
  15.     #define all(c) (c).begin(),(c).end() 
  16.     #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
  17.     #define present(c,x) ((c).find(x) != (c).end()) 
  18.     #define cpresent(c,x) (find(all(c),x) != (c).end()) 
  19.     #define p(a) cout << a << "\n";
  20.     long n;
  21.     vector<pair<int,long > > vec[100005];
  22.     int mindistance(ll dist[], bool spt[])
  23.     {
  24.         long min = INT_MAX, min_index;
  25.         for(ll v = 0; v <= n; ++v)
  26.         {
  27.             if(spt[v] == false && dist[v] <= min)
  28.             {
  29.                 min = dist[v];
  30.                 min_index = v;
  31.             }
  32.         }
  33.         return min_index;
  34.     }
  35.     void dijkstra(vector<pair<int,long> > *vec, long s)
  36.     {
  37.         ll dist[n+1];
  38.         bool spt[n+1];
  39.         for(int i = 0; i <= n; ++i)
  40.         {
  41.                 dist[i] = INT_MAX;
  42.                 spt[i] = false;
  43.         }
  44.         dist[s] = 0;
  45.         for(int i = 0; i < n; ++i)
  46.         {
  47.             int u = mindistance(dist, spt);
  48.             spt[u] = true;
  49.             for(int j = 0; j < vec[u].size(); ++j)
  50.             { 
  51.                 if(!spt[vec[u][j].first] && dist[u] != INT_MAX && dist[u]+vec[u][j].second < dist[vec[u][j].first])
  52.                 {
  53.                     dist[vec[u][j].first] = dist[u] + vec[u][j].second;
  54.                 }
  55.             }
  56.         }
  57.         for(int i = 1; i <= n; ++i)
  58.         {
  59.             printf("%lld ", dist[i]/2);
  60.         }   
  61.         printf("\n");
  62.     }
  63.     void solve()
  64.     {
  65.         long k,x,m,s,a,b,c;
  66.         int t;
  67.         scanf("%d",&t);
  68.         while(t--)
  69.         {
  70.             scanf("%ld %ld %ld %ld %ld",&n,&k,&x,&m,&s);
  71.             iloop(1,n+1)
  72.             vec[i].clear();
  73.             iloop(1,k+1)
  74.             {
  75.                 vec[i].pb(mp(0,x));
  76.                 vec[0].pb(mp(i,x));
  77.             }
  78.             iloop(0,m)
  79.             {
  80.                 scanf("%ld %ld %ld",&a,&b,&c);
  81.                 vec[a].pb(mp(b,2*c));
  82.                 vec[b].pb(mp(a,2*c));
  83.             }
  84.             dijkstra(vec, s);
  85.         }
  86.     }
  87.     int main()
  88.     {
  89.         bool testing = false;
  90.         std::ios::sync_with_stdio(false);
  91.         cin.tie(NULL);
  92.         cout.tie(NULL);
  93.         if(testing)
  94.         {
  95.             freopen("test.txt","rt",stdin);
  96.             int start = clock();
  97.             solve();
  98.             int end = clock();
  99.             cout << "time: " << (end - start)/(double)(CLOCKS_PER_SEC)*1000 << " milliseconds\n";
  100.         }
  101.         else
  102.         {
  103.             solve();
  104.         }
  105.     }
Runtime error #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6KfQWj
language:
C++14 (gcc 8.3)
created:
7 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!