URAL1004[Sightseeing trip]

Floyd求最小环。

CODE:

/*
PROGRAM: \$PROGRAM
AUTHOR: Su Jiao
DATE: 2010-3-10
DESCRIPTION:
\$DESCRIPTION
*/
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <vector>
using std::vector;
#include <map>
//using std::map;
#include <stack>
using std::stack;
#include <queue>
using std::queue;
using std::pair;
using std::make_pair;
#include <cassert>
//using std::assert;

class Question
{

static const int oo=1<<29;
vector<vector<
int> > map;

void print(stack<int>& s,vector<vector<int> >& mid,int u,int v)
{

if (mid[u][v]<0)
{

if (s.top()!=u) s.push(u);

if (s.top()!=v) s.push(v);
}

else
{
print(s,mid,u,mid[u][v]);
print(s,mid,mid[u][v],v);
}
}

public:

{

int N,M;
cin>>N;

if (N==-1) return false;
cin>>M;

map.resize(N,vector<
int>(N,oo));

for (int i=0;i<M;i++)
{

int u,v,l;
cin>>u>>v>>l;
u–;
v–;

//assert(u<N&&v<N);
if (map[u][v]>l) map[u][v]=l;

if (map[v][u]>l) map[v][u]=l;
}

return true;
}

void solve()
{
vector<vector<
int> > dist,mid;

dist=map;
mid.resize(dist.size(),vector<
int>(dist.size(),-1));

int min=oo;

int min_i,min_j,min_k;

for (int k=0;k<dist.size();k++)
{

for (int i=0;i<k;i++)

for (int j=i+1;j<k;j++)
{

//assert(i!=j&&i!=k&&j!=k);
if (min>(dist[j][i]+map[i][k]+map[k][j]))
{
min=dist[j][i]+map[i][k]+map[k][j];
min_i=i;
min_j=j;
min_k=k;
}
}

for (int i=0;i<dist.size();i++)

for (int j=0;j<dist.size();j++)

if (dist[i][j]>dist[i][k]+dist[k][j])
dist[i][j]=dist[i][k]+dist[k][j];
}

if (min<oo)
{
dist=map;
dist[min_i][min_k]=dist[min_k][min_i]=oo;
dist[min_j][min_k]=dist[min_k][min_j]=oo;

for (int k=0;k<dist.size();k++)

for (int i=0;i<dist.size();i++)

for (int j=0;j<dist.size();j++)

if (dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
mid[i][j]=k;
}

stack<
int> s;

s.push(min_k);
print(s,mid,min_i,min_j);

for (;;)
{
cout<<s.top()+
1;
s.pop();

if (s.empty())
{
cout<<endl;

break;
}

else cout<<” “;
}
}

else cout<<“No solution.”<<endl;

map.clear();
}
};

class Application
{

public:
Application()
{
}

int run()
{
Question q;