poj 1734 Sightseeing trip(floyd最小ループを求めて経路を記録する)
5344 ワード
クリックしてタイトルリンクを開く
Description
There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route. 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
The first line of input contains two positive integers: the number of crossing points N<=100 and the number of roads M<=10000. Each of the next M lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than 500).
Output
There is only one line in output. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x_1 to x_k from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.
Sample Input
Sample Output
1 3 5 2
タイトル:
nつの都市があって、m本の道があって、それぞれの道は2つの都市を接続してしかも一定の費用があって、あなたの任務は1本の起点からまた起点に戻る経路を探し出して、経路の上ですべての費用が最小になって、しかもこの経路は少なくとも3つ以上の異なる都市があって、もしv 1から始まるならば、v 1->v 2->....->vk,vkは再びv 1に戻る、kは2より大きく、出力フォーマットはv 1 v 2...である.vk
ここで、n<=100、m<=10000であり、各経路に500以下の費用がかかる.
解析:パスを出力しない場合、この問題はfloydが最小ループを求める問題であるが、この問題は最小ループが通過する点を出力する必要があるので、元の最小ループを求める上で配列記録パスを追加し、別の配列pa[i][j]=xを開くとi->を表す......->x->jは、pa[i][j]がi->jという経路上のjの前の点がどれであるかを意味する.
初期化時pa[i][j]=iであることは明らかである.
ではどのようにdpで移動するのか、floydを求める最短ルートを振り返ると、dis[i][j]>dis[i][k]+dis[k][j]であれば、dis[i][j]=dis[i][k]+dis[k][j]となり、このときにpaを同時に移動させ、pa[i][j]=pa[k][j]となるようにすることができます.pa[i][k]とpa[k][j]はすでに求められているので、直接移行します.
転送が完了し、次の仕事はどのように答えを記録し、出力するかです.floydが最小ループを求めて答えを記録するときに経路を記録するだけです.
具体的な操作コードの実現:
Description
There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route. 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
The first line of input contains two positive integers: the number of crossing points N<=100 and the number of roads M<=10000. Each of the next M lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than 500).
Output
There is only one line in output. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x_1 to x_k from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.
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
タイトル:
nつの都市があって、m本の道があって、それぞれの道は2つの都市を接続してしかも一定の費用があって、あなたの任務は1本の起点からまた起点に戻る経路を探し出して、経路の上ですべての費用が最小になって、しかもこの経路は少なくとも3つ以上の異なる都市があって、もしv 1から始まるならば、v 1->v 2->....->vk,vkは再びv 1に戻る、kは2より大きく、出力フォーマットはv 1 v 2...である.vk
ここで、n<=100、m<=10000であり、各経路に500以下の費用がかかる.
解析:パスを出力しない場合、この問題はfloydが最小ループを求める問題であるが、この問題は最小ループが通過する点を出力する必要があるので、元の最小ループを求める上で配列記録パスを追加し、別の配列pa[i][j]=xを開くとi->を表す......->x->jは、pa[i][j]がi->jという経路上のjの前の点がどれであるかを意味する.
初期化時pa[i][j]=iであることは明らかである.
ではどのようにdpで移動するのか、floydを求める最短ルートを振り返ると、dis[i][j]>dis[i][k]+dis[k][j]であれば、dis[i][j]=dis[i][k]+dis[k][j]となり、このときにpaを同時に移動させ、pa[i][j]=pa[k][j]となるようにすることができます.pa[i][k]とpa[k][j]はすでに求められているので、直接移行します.
転送が完了し、次の仕事はどのように答えを記録し、出力するかです.floydが最小ループを求めて答えを記録するときに経路を記録するだけです.
具体的な操作コードの実現:
#include<Stdio.h>
#include<string.h>
#include<algorithm>
#define inf 1e8
using namespace std;
int dis[110][110];///
int pa[110][110];/// i>j
int ma[110][110];///
int ans[110];/// （ ）
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dis[i][j]=ma[i][j]=inf;
pa[i][j]=i;
}
}
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(ma[x][y]>c)///
{
ma[x][y]=dis[x][y]=c;
ma[y][x]=dis[y][x]=c;
}
}
int minn=inf,num;///num
for(int k=1;k<=n;k++)
{
/// k ， k ，i j k ，
for(int i=1;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
if(minn>dis[i][j]+ma[k][i]+ma[k][j])
{
num=0;///
minn=dis[i][j]+ma[k][i]+ma[k][j];
int posi=i,posj=j;
ans[++num]=j;
while(1)/// ，
{
posj=pa[posi][posj];
num++;
ans[num]=posj;
if(posi==posj) break;
}
ans[++num]=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];
pa[i][j]=pa[k][j];
}
}
}
}
if(minn==inf)
{
puts("No solution.");
continue;
}
for(int i=num;i>=2;i--) printf("%d ",ans[i]);
printf("%d
",ans[1]);
}
return 0;
}