fork(1) download
copy 
  1.     //Templet start
  2.     #include <stdio.h>
  3.     #include <stdlib.h>
  4.     #include <string.h>
  5.     #include <math.h>
  6.     #include <ctype.h>
  7.     #include <string>
  8.     #include <iostream>
  9.     #include <sstream>
  10.     #include <vector>
  11.     #include <queue>
  12.     #include <stack>
  13.     #include <map>
  14.     #include <list>
  15.     #include <algorithm>
  16.  
  17.     using namespace std;
  18.  
  19.     #define sf scanf
  20.     #define pf printf
  21.     #define long long lld
  22.     #define llu unsigned long long
  23.     #define fo(i, n) for(i = 0; i < n; i++)
  24.     #define of(i, n) for(i = n - 1; i >= 0; i--)
  25.     #define mem(n, v) memset(n, v, sizeof( n ))
  26.     #define eps 1e-8
  27.     #define INF 5000
  28.     #define pb push_back
  29.     #define maxn 200+2
  30.  
  31.     #define white 0
  32.     #define black 1
  33.  
  34.     typedef pair<int, int> pii;
  35.     typedef  vector<int> vi;
  36.     typedef vector<pii> vii;
  37.  
  38.  
  39.     int diraction1[] = {-1, 0, 0, 1, 1, -1, -1, 1};
  40.     int diraction2[] = {0, -1, 1, 0, 1, -1, 1, -1};
  41.     int horsed1[] = {-2, -2, -1, 1, 2, 2, 1, -1};
  42.     int horsed2[] = {1, -1, -2, -2, -1, 1, 2, 2};
  43.  
  44.     //Templet end
  45.     void input();
  46.     void reset();
  47.     void BFS(int u);
  48.  
  49.     struct data
  50.     {
  51.         int u, cost;
  52.         data() {}
  53.  
  54.         bool operator < (const data& s) const
  55.         {
  56.             return cost < s.cost;
  57.         }
  58.     };
  59.  
  60.     int node, edge, parents[ maxn ], cc[ maxn ];
  61.     vector <vii> graph;
  62.     map <string, int> m;
  63.     char s[ 32 ], e[ 32 ];
  64.     bool mark[ maxn ];
  65.  
  66.     int main()
  67.     {
  68.         input();
  69.  
  70.         return 0;
  71.     }
  72.     void input()
  73.     {
  74.         int i, j, k, src, end, cst, res, kag = 0;
  75.         while(~sf("%d %d", &node, &edge))
  76.         {
  77.             if(!node && !edge) break;
  78.             k = 1;
  79.             reset();
  80.             // get input
  81.             fo(i, edge)
  82.             {
  83.                 mem(s, 0); mem(e, 0);
  84.                 sf("%s %s %d", s, e, &cst);
  85.                 if(!m[ s ]) m[ s ] = k++;
  86.                 if(!m[ e ]) m[ e ] = k++;
  87.                 graph[ m[ s ] ].pb( pii(m[ e ], cst) );
  88.                 graph[ m[ e ] ].pb( pii(m[ s ], cst) );
  89.             }
  90.             mem(s, 0); mem(e, 0);
  91.             sf("%s %s", s, e);
  92.             //*******************************
  93.             if(m[ s ] == m[ e ])
  94.             {
  95.                 pf("Scenario #%d\n0 tons\n\n", ++kag);
  96.                 continue;
  97.             }
  98.             BFS( m[ s ] );
  99.             int ss = m[ e ];
  100.             // find the result
  101.             res = cc[ ss ];
  102.             while(true)
  103.             {
  104.                 ss = parents[ ss ];
  105.                 if(ss == m[ s ])
  106.                 {
  107.                     break;
  108.                 }
  109.                 res = min(res, cc[ ss ]);
  110.             }
  111.             //**********************
  112.             pf("Scenario #%d\n%d tons\n\n", ++kag, res);
  113.         }
  114.     }
  115.     void BFS(int u)
  116.     {
  117.         int i, j, tmp, wait;
  118.         priority_queue <data> Q;
  119.         data x;
  120.         x.u = u; x.cost = 0;
  121.         Q.push( x );
  122.         mark[ u ] = false;
  123.         while(!Q.empty())
  124.         {
  125.             x = Q.top(); Q.pop();
  126.             u = x.u;
  127.             wait = x.cost;
  128.             for(i = 0; i < graph[ u ].size(); i++)
  129.             {
  130.                 pii pr = graph[ u ][ i ];
  131.                 if(mark[ pr.first ])
  132.                 {
  133.                     parents[ pr.first ] = u;
  134.                     cc[ pr.first ] = pr.second; // i use cc[] for save the paths cost
  135.                     mark[ pr.first ] = false;
  136.                     x.u = pr.first; x.cost = pr.second;
  137.                     Q.push( x );
  138.                     if(pr.first == m[ e ]) // when i find the end point then stop
  139.                     {
  140.                         while(!Q.empty()) Q.pop();
  141.                         i = graph[ u ].size();
  142.                     }
  143.                 }
  144.             }
  145.         }
  146.     }
  147.     void reset()
  148.     {
  149.         m.clear();
  150.         graph.assign(node+1, vii());
  151.         int i;
  152.         for(i = 1; i <= node; i++)
  153.         {
  154.             parents[ i ] = -1;
  155.             mark[ i ] = true;
  156.             cc[ i ] = -1;
  157.         }
  158.         mark[ 0 ] = true;
  159.     }
  160.  
Success #stdin #stdout 0s 2836KB
comments (?)
stdin
copy 
4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
6 7
A B 5
B C 10
A C 3
C D 1
C E 2
C F 4
E F 9
0 0
stdout
copy 
Scenario #1
80 tons

Scenario #2
170 tons

Scenario #3
0 tons
https://ideone.com/ykUSR9
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
secret

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!