fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define nmk ios::sync_with_stdio(5+2==2006); cin.tie(0); cout.tie(0);
  4. #define ll long long
  5. #define maxn 2005
  6. const ll oo=4e18;
  7. vector<pair<int,int>>ke[maxn];
  8. ll d[2][maxn];
  9. struct node{
  10.     ll w;
  11.     int state;
  12.     int v;
  13.     bool operator>(const node& other) const {
  14.         return w > other.w;
  15.     }
  16. };
  17.  
  18. int main(){
  19.     nmk;
  20.     int n,m,test;cin>>n>>m>>test;
  21.     for (int i=1;i<=m;i++){
  22.         int u,v,t;cin>>u>>v>>t;
  23.         ke[u].push_back({t,v});
  24.     }
  25.     //
  26.     for (int i=1;i<=n;i++){
  27.         d[0][i]=oo;
  28.         d[1][i]=oo;
  29.     }
  30.     d[0][1]=d[1][1]=0;
  31.     //
  32.     priority_queue<node,vector<node>,greater<node>> q;
  33.     q.push({0,0,1});
  34.     while (!q.empty()){
  35.         auto t=q.top();q.pop();
  36.         int u=t.v; ll w=t.w; int state=t.state;
  37.         if (w>d[state][u]) continue;
  38.         for (auto tmp:ke[u]){
  39.             int v=tmp.second, di=tmp.first;
  40.  
  41.             //ko cat doan uv;
  42.             if (d[state][v]>w+di){
  43.                 d[state][v]=w+di;
  44.                 q.push({d[state][v],state,v});
  45.             }
  46.             //neu chua cat thi cat thu
  47.             if (state==0){
  48.                 if (d[1][v]>w){
  49.                     d[1][v]=w;
  50.                     q.push({d[1][v],1,v});
  51.                 }
  52.             }
  53.  
  54.         }
  55.     }
  56.  
  57.  
  58.     while (test--){
  59.         int s,t0;cin>>s>>t0;
  60.         cout<<min(d[0][s],d[1][s]+t0)<<"\n";
  61.     }
  62.  
  63.     return 0;
  64. }
  65.  
Runtime error #stdin #stdout 0.05s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0YwpkS
language:
C++ (gcc 8.3)
created:
24 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!