fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9.     ios::sync_with_stdio(0);
  10.  
  11.     int n,m,s,e;
  12.     bool can[40][40];
  13.     string M[40][40],str;
  14.     string loop[40];
  15.  
  16.     while(true){
  17.         cin >> n >> m >> s >> e;
  18.  
  19.         if(n == 0) break;
  20.  
  21.         for(int i = 0;i < n;++i)
  22.             loop[i] = "zzzzzzz";
  23.  
  24.         memset(can,0,sizeof can);
  25.  
  26.         for(int i = 0,u,v;i < m;++i){
  27.             cin >> u >> v >> str;
  28.  
  29.             if(u == v) loop[u] = min(loop[u],str);
  30.             else{
  31.                 if(!can[u][v]) M[u][v] = str;
  32.                 else M[u][v] = min(M[u][v],str);
  33.  
  34.                 can[u][v] = true;
  35.             }
  36.         }
  37.  
  38.         for(int k = 0;k < n;++k)
  39.             for(int i = 0;i < n;++i)
  40.                 for(int j = 0;j < n;++j)
  41.                     if(can[i][k] && can[k][j]){
  42.                         if(!can[i][j]) M[i][j] = M[i][k] + M[k][j];
  43.                         else M[i][j] = min(M[i][j],M[i][k] + M[k][j]);
  44.  
  45.                         can[i][j] = true;
  46.                     }
  47.  
  48.         for(int i = 0;i < n;++i)
  49.             for(int j = 0;j < n;++j)
  50.                 if(j != i && can[i][j] && can[j][i])
  51.                     loop[i] = min(loop[i],M[i][j] + M[j][i]);
  52.  
  53.         if(!can[s][e]) cout << "NO\n";
  54.         else{
  55.             bool ok = true;
  56.  
  57.             if(loop[s] + M[s][e] < M[s][e]) ok = false;
  58.  
  59.             for(int i = 0;i < n;++i){
  60.                 if(i != s && i != e && can[s][i] && can[i][e] && M[s][i] + loop[i] + M[i][e] < M[s][e])
  61.                     ok = false;
  62.             }
  63.  
  64.             if(!ok) cout << "NO\n";
  65.             else cout << M[s][e] << '\n';
  66.         }
  67.     }
  68.  
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0.01s 2864KB
comments (?)
stdin
copy 
4 7 0 2
0 1 abra
0 1 oil
2 0 ket
1 3 cada
3 3 da
3 2 bra
2 3 ket
2 2 0 1
0 0 a
0 1 b
5 6 3 0
3 1 op
3 2 op
3 4 opq
1 0 st
2 0 qr
4 0 r
2 1 0 1
1 1 loooop
3 3 0 2
0 1 a
0 1 ab
1 2 c
0 0 0 0
stdout
copy 
abracadabra
NO
opqr
NO
ac
https://ideone.com/po0pu
language:
C++ (gcc 8.3)
created:
12 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!