1436 Renting Boats

Accept: 225Submit: 485
Time Limit: 1000 mSecMemory Limit : 32768 KB

Problem Description

Yangtse Rive Barge Club has set up n barge hiring stops numbered 1, 2, … , n along the Changjiang River. Passengers can hire barges from any of these stops, and return the barges to one of the stops afterward. The rent for an barge from stop i to stop j is r(i,j) (1<=i,j<=n). Your task is to design an algorithm to minimize the rent of hiring barges when you traveling from stop 1 to stop n.

Input

There are multiple test cases. The first line of each case contains an integer n indicating the number of the stops (n<=200). The following n-1 lines are the rent between any two stops. The ith following line contains n-i integers indicating r(i,j) (i < j <= n).

Output

For each case, output one line representing the minimal rent.

Sample Input

3

5 15

7

Sample Output

12

思路:

题目的意思就是求从停泊点1到n的最少费用

就是求单点源最短路径的问题, 用dijkstra算法

如果存在<Vi,Vj>则map[Vi][Vj]=权值(这里就是vi->vj的费用)

如果不存在初始化为INF(无穷大)

dist[i]数组用来存放源点1到点i的最少费用,

s[i]用来标记源点1到点i的最少费用是否算出

#include<stdio.h>
#define INF 99999999
#define MAX 201
int map[MAX][MAX];
int s[MAX],dist[MAX];
int mindist;
void dijkstra(int n)
{
	int i,j,k,v0=1;
	for(i=1;i<=n;i++)	//初始化
	{
		dist[i]=map[v0][i];
		s[i]=0;
	}
	s[v0]=1;
	for(i=1;i<=n;i++)
	{
		mindist=INF;
		k=v0;
		for(j=1;j<=n;j++)
		{
			if(s[j]==0 && dist[j]<mindist)
			{
				k=j;
				mindist=dist[j];
			}
		}
		s[k]=1;
		for(j=1;j<=n;j++)
		{
			if(s[j]==0)
				if(map[k][j]<INF && dist[k]+map[k][j]<dist[j])
					dist[j]=dist[k]+map[k][j];
		}
	}
}
int main()
{
	int i,j,n;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				map[i][j]=INF;
		for(i=1;i<=n-1;i++)
			for(j=i+1;j<=n;j++)
				scanf("%d",&map[i][j]);
		dijkstra(n);
		printf("%d/n", dist[n]);
	}
	return 0;
}