| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 6647 | Accepted: 2538 | Special Judge | ||
Description
In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different.The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible,because there is no sightseeing route in the town.
Input
Output
Sample Input
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
Sample Output
1 3 5 2
Source
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=105;
const int INF=1e6;//改成1e9就不对了
int dis[MAXN][MAXN],mp[MAXN][MAXN];
int R[MAXN][MAXN],path[MAXN];
int N,M,len;
int u,v,w;
int cnt=0;
void Init()
{
for(int i=0;i<=N;i++)
for(int j=0;j<=N;j++)
dis[i][j]=INF,R[i][j]=0;
cnt=0;
}
void Path(int s,int t)
{
if(R[s][t])
{
Path(s,R[s][t]);
Path(R[s][t],t);
}
else
path[++cnt]=t;
}
void Floyd()
{
len=INF;
for(int k=1;k<=N;k++)
{
//判断负环
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
{
if(len>dis[i][j]+mp[i][k]+mp[k][j])
{
len=dis[i][j]+mp[i][k]+mp[k][j];
cnt=0;
path[++cnt]=i;
Path(i,j);
path[++cnt]=k; }
}
//求最短路
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
R[i][j]=k;
}
}
}
}
int main ()
{
while(~scanf("%d%d",&N,&M))
{
Init();
for(int i=1;i<=M;i++)
{
scanf("%d%d%d",&u,&v,&w);
if(dis[u][v]>w)//记录重边
{
dis[u][v]=w;
dis[v][u]=w;
}
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
mp[i][j]=dis[i][j];//mp判断环的时候要用到
Floyd();
if(len==INF)
printf("No solution.\n");
else
{
for(int i=1;i<=cnt;i++)
{
if(i!=cnt)
printf("%d ",path[i]);
else
printf("%d\n",path[i]);
}
}
}
return 0;
}