fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. long long q,m,n=0,c,u,v,w,price[222];
  5. vector<pair<int,long long> >l[222];
  6. struct cmp{
  7.     bool operator()(pair<int,long long>x,pair<int,long long>y)
  8.     {
  9.         return x.second>y.second;
  10.     }
  11. };
  12. priority_queue<pair<int,long long>,vector<pair<int,long long> >,cmp>s;
  13. pair<int,long long>tam,temp;
  14. int main()
  15. {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.     cin>>q;
  20.     while(q--)
  21.     {
  22.         for(int i=1; i<222; i++)
  23.             l[i].clear();
  24.         cin>>n>>m>>c;
  25.         for(int i=1; i<=n; i++)
  26.             price[i]=1e18;
  27.         for(int i=1; i<=m; i++)
  28.         {
  29.             cin>>u>>v>>w;
  30.             l[u].push_back({v,w});
  31.             l[v].push_back({u,w});
  32.         }
  33.         price[n]=0;
  34.         s.push({n,0});
  35.         while(!s.empty())
  36.         {
  37.             tam=s.top();
  38.             s.pop();
  39.             if(tam.second!=price[tam.first])continue;
  40.             u=tam.first;
  41.             for(int i=0; i<l[u].size(); i++)
  42.             {
  43.                 temp=l[u][i];
  44.                 long long need=tam.second,ca=temp.second;
  45.                 if(need+ca<=c)temp.second=need+ca;
  46.                 else
  47.                 {
  48.                     if(c<=2*ca)continue;
  49.                     long long t=(need+ca-c)/(c-2*ca);
  50.                     if((need+c-ca)%(c-2*ca)!=0)t++;
  51.                     temp.second=(2*t+1)*ca+need;
  52.                 }
  53.                 if(price[temp.first]>temp.second)
  54.                 {
  55.                     price[temp.first]=temp.second;
  56.                     s.push(temp);
  57.                 }
  58.             }
  59.         }
  60.         cout<<price[1]<<'\n';
  61.     }
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
1
9 10 25
1 2 3
2 3 12
3 4 4
3 5 9
4 9 13
5 9 5
2 6 10
6 7 10
7 8 10
8 9 10
stdout 
65
https://ideone.com/Vaz5Xi
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!