fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define data DATA
  3. #define pii pair<int,int>
  4. #define F first
  5. #define S second
  6. #define pb push_back
  7. #define maxn 3000
  8. using namespace std;
  9. struct data
  10. {
  11.     int v;
  12. };
  13. vector<pii> line[maxn];
  14. int n,d[maxn];
  15.  
  16. void nhap()
  17. {
  18.     cin>>n;
  19.     int u;
  20.     while(cin>>u)
  21.     {
  22.         int v,w1,w2;
  23.         char s;
  24.         cin>>v>>w1>>w2>>s;
  25.         if (s=='G')
  26.         {
  27.             line[u].pb({v+n,w1});
  28.             line[v+n].pb({u,w2});
  29.         }
  30.         else if (s=='M')
  31.         {
  32.             line[u+n].pb({v,w1});
  33.             line[v].pb({u+n,w2});
  34.         }
  35.     }
  36. }
  37.  
  38. int IJK()/// d[maxn] is all
  39. {
  40.     memset(d,30,sizeof d);
  41.     d[1]=d[n+1]=0;
  42.     priority_queue<pii>q;
  43.     q.push({0,1});q.push({0,n+1});
  44.     while(!q.empty())
  45.     {
  46.         //Tim dinh U co d[u] min
  47.         int u=q.top().S;
  48.         int w=-q.top().F;
  49.         q.pop();
  50.         if (w>d[u]) continue;
  51.         if (u==n||u==n+n) return d[n];
  52.  
  53.         for(auto j:line[u])
  54.         {
  55.             int v=j.F;
  56.             int w=j.S;
  57.             if (d[v]>d[u]+w)
  58.             {
  59.                 d[v]=d[u]+w;
  60.                 q.push({-d[v],v});
  61.             }
  62.         }
  63.  
  64.     }
  65. }
  66.  
  67.  
  68. int main()
  69. {
  70.     ios_base::sync_with_stdio(0);
  71.         cin.tie();
  72.         cout.tie();
  73.     if (fopen("in.txt","r"))
  74.         {
  75.             freopen("in.txt","r",stdin);
  76.  
  77.         }
  78.     nhap();
  79.     cout<<IJK();
  80. }
  81.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
5
1 2 3 3 M
1 4 4 4 G
1 3 2 2 G
2 5 3 3 G
2 4 10 10 G
5 4 1 1 G
4 3 1 1 M
stdout
copy 
5
https://ideone.com/4wJiAb
language:
C++ (gcc 8.3)
created:
16 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!