Trip |
||
|
||
description |
||
Xiao wang has a new car, so he wants to have a trip from his home to hefei, however, there is no road from his house directly to Hefei, so he has to go through a number of cities to get to hefei, his car takes one unit of time driving a unit distance at first, but his car will be slow after every city that he pass, so he will take one more unit of time to take a unit of distance after every city (that is, if he has passed k cities, then he needs k units of time to take a unit of distance, we think his home is the first city), can you tell him how to spend the least time to reach Hefei?
|
||
input |
||
The first line contains two numbers n and m (0 < n ≤ 200, 0 < m < n×(n-1)/2 ), n is the number of city, 1 is xiaowang's home, n is hefei, m is the number of road, bi-directional edge, then the following m line contains 3 numbers x, y, z, means there is a road from x to y, the distance is z.(You can make sure that there is always a path exist between his home ande hefei).
|
||
output |
||
The least time xiao wang must use from his home to hefei.
|
||
sample_input |
||
5 6
1 2 1
1 4 5
2 3 2
3 5 1
4 5 1
2 4 2
|
||
sample_output |
||
7
|
f[i][j]表示经过i个点从1到达j所用的最短距离。
f[i][k]=min(f[i-1][j]+i*a[j][k])，即经过i个点从1到达k所用的最短距离等于经过i-1个点从j到达k的最小值(1<j<n)。
-----------------------------------------------------------------------------------------
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
const int OO=1e9;
long long a[222][222];
long long f[222][222];
int main()
{
while (~scanf("%d%d",&n,&m))
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
a[i][j]=f[i][j]=OO;
}
}
for (int i=1; i<=m; i++)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
a[u][v]=a[v][u]=c;
if(u==1) f[1][v]=c;
if(v==1) f[1][u]=c;
}
long long _min=a[1][n];
for(int i=2; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(f[i-1][j]!=OO)
{
for(int k=1; k<=n; k++)
{
if(f[i-1][j]+i*a[j][k]<f[i][k])
{
f[i][k]=f[i-1][j]+i*a[j][k];
}
}
}
}
}
for(int i=1; i<=n-1; i++)
{
if(f[i][n]<_min) _min=f[i][n];
}
printf("%I64d\n",_min);
}
return 0;
}