lib/Documentation/docs-sonyckson/1004.cpp

   1 // UN DIJKSTRA QUE GUARDA CAMINOS.... NO ES TAN TIVIAL COMO APARENTA... IMP
   2
   3
   4 #include <algorithm>
   5 #include <vector>
   6 #include <set>
   7 #include <string>
   8 #include <fstream>
   9 #include <iostream>
  10 #include <iomanip>
  11 #include <map>
  12 #include <stack>
  13 #include <sstream>
  14 #include <queue>
  15
  16 #include <cmath>
  17 #include <cstdio>
  18 #include <cctype>
  19 #include <cstdlib>
  20 #include <cstring>
  21 #include <cassert>
  22 #define forn(i, n) for(int i=0;i<int(n);i++)
  23 #define foreach(it, c)  for(typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  24 #define ALL(x)   (x).begin(),(x).end()
  25 #define SORT(x) sort(ALL(x))
  26 using namespace std;
  27 #define VI vector<int>
  28 #define VS vector<string>
  29 #define PB push_back
  30 #define ll long long
  31 #define MX 1000000
  32 int main(){
  33         int i,j ,k;
  34         int N, M;
  35         while(1){
  36                 VI edges[101];
  37                 int cost[101][101];
  38                 scanf("%i", &N);if( N < 0 ) return 0;
  39                 for(i=0;i<=N;i++)for(j=0;j<=N;j++) cost[i][j] = MX;
  40                 scanf("%i", &M);int a, b, c;
  41                 for(i=0;i<M;i++){
  42                         scanf("%i %i %i", &a, &b, &c);
  43                         if( a > N || b > N ) continue;
  44                         edges[a].PB(b), edges[b].PB(a);
  45                         cost[a][b] = min(cost[a][b], c);
  46                         cost[b][a] = min(cost[b][a],c);
  47                 }
  48                 VI res;
  49                 int sum = INT_MAX;
  50                 for(i=1;i<=N;i++)for(j=i+1;j<=N;j++){
  51                         if( cost[i][j] == MX ) continue;
  52                         set<pair<int,int> > Q;
  53                         Q.insert(make_pair(0, i));
  54                         int visited[102];
  55                         memset(visited, 0, sizeof(visited));
  56                         int mark[102];
  57                         for(k=0;k<102;k++) mark[k] = MX;
  58                         int padre[102];
  59                         memset(padre, -1, sizeof(padre));
  60                         while(!Q.empty()){
  61                                 pair<int,int> par = *(Q.begin()); Q.erase(Q.begin());
  62                                 if( par.second == j ) break;
  63                                 if( cost[i][j] + par.first >= sum ) break;
  64                                 if( visited[par.second] || par.first > mark[par.second] ) continue;
  65                                 visited[par.second] = 1;
  66                                 for(k=0;k<edges[par.second].size();k++){
  67                                         if( par.second ==  i ){
  68                                                 if( edges[par.second][k] == j ) continue;
  69                                         }if( edges[par.second][k] == i ){
  70                                                 if( par.second == j ) continue;
  71                                         }
  72                                         int dist = cost[par.second][edges[par.second][k]] + par.first;
  73                                         if( dist < mark[edges[par.second][k]] ){
  74                                                 mark[edges[par.second][k]] = dist;
  75                                                 Q.insert(make_pair(dist, edges[par.second][k]));
  76                                                 padre[edges[par.second][k]] = par.second;
  77                                         }
  78                                 }
  79                         }
  80                         int tot = mark[j] + cost[i][j];
  81                         if( tot < sum && padre[j] > 0){
  82                                 VI aux;
  83                                 int ind = j;
  84                                 while(ind != i){
  85                                         aux.PB(ind);
  86                                         ind = padre[ind];
  87                                 }
  88                                 aux.PB(i);
  89                                 res = aux;
  90                                 sum = tot;
  91                         }
  92                 }
  93                 if( sum < MX ){
  94                         int first = 1;
  95                         for(i=0;i<res.size();i++){
  96                                 if( first ) first = 0; else printf(" ");
  97                                 printf("%i", res[i]);
  98                         }
  99                         printf("\n");
 100                 }else printf("No solution.\n");
 101         }
 102         return 0;
 103 }