Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Apr 28th, 2012  |  syntax: C++  |  size: 1.80 KB  |  hits: 19  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <vector>
  5. #define get(i) scanf("%d",&i);
  6.  
  7. using namespace std;
  8.  
  9. const int maxn = 101;
  10. int edge[maxn][maxn];
  11. int parent[maxn];
  12. bool used[maxn];
  13.  
  14. const int inf = 1<<30;
  15. int n ,m;
  16.  
  17. int dijkstra(int from,int to)
  18. {
  19.         int d[maxn],mind,mini;
  20.         for(int i= 0;i<=n;i++)
  21.                 d[i]=(i==from)?0:inf;
  22.         memset(used,false,sizeof(used));
  23.         memset(parent,0,sizeof(parent));
  24.         for(int i = 1;i<=n;i++)
  25.         {
  26.                 mind = inf;mini = 0;
  27.                 for(int j = 1;j<=n;j++)
  28.                 {
  29.                         if(!used[j] && (mind>d[j]))
  30.                         {
  31.                                 mind = d[j];mini = j;
  32.                         }
  33.                 }
  34.                 if(mind == inf)return d[to];
  35.                 used[mini]=true;
  36.                 for(int j = 1;j<=n;j++)
  37.                 {
  38.                         if(!used[j] && d[j]>d[mini]+edge[mini][j])
  39.                         {
  40.                                 d[j]=d[mini]+edge[mini][j];
  41.                                 parent[j]=mini;
  42.                         }
  43.                 }
  44.         }
  45.         return d[to];
  46. }
  47. int path[maxn];
  48. int pathsize;
  49.  
  50. int main()
  51. {
  52.         freopen("input.txt","r",stdin);
  53.         freopen("output.txt","w",stdout);
  54.         int a,b,w;
  55.         cin>>n;
  56.         while(n!=-1)
  57.         {
  58.                 cin>>m;
  59.                 for(int i = 1;i<=n;i++)
  60.                         for(int j = 1;j<=n;j++)
  61.                                 edge[i][j]=inf;
  62.                 int ans = inf;
  63.                 for(int i = 0;i<m;i++)
  64.                 {
  65.                         get(a);get(b);get(w);
  66.                         if(edge[a][b]>w)
  67.                         edge[a][b]=edge[b][a]=w;
  68.                         for(int j = 1;j<=n;j++)
  69.                                 for(int k = j+1;k<=n;k++)
  70.                                 {
  71.                                         if(edge[j][k] == inf)continue;
  72.                                         int cur= edge[j][k];
  73.                                         edge[j][k]=edge[k][j] = inf;
  74.                                         int curans = cur+dijkstra(j,k);
  75.                                         if(ans>curans)
  76.                                         {
  77.                                                 ans = curans;
  78.                                                 pathsize = 0;
  79.                                                 int r = k;
  80.                                                 while(r)
  81.                                                 {
  82.                                                         path[pathsize++]=r;
  83.                                                         r = parent[r];
  84.                                                 }
  85.                                         }
  86.                                         edge[j][k]=edge[k][j] = cur;
  87.                                 }
  88.                 }
  89.                 if(ans == inf)
  90.                 {
  91.                         cout<<"No solution.\n";
  92.                 }
  93.                 else
  94.                 {
  95.                         for(int i = pathsize-1;i>=0;i--)
  96.                         {
  97.                                 cout<<path[i];
  98.                                 if(i!=0)cout<<" ";
  99.                         }
  100.                         cout<<endl;
  101.                 }
  102.                 cin>>n;
  103.         }
  104.         return 0;
  105. }
create a new version of this paste RAW Paste Data