2014
02-13

Choose the best route

One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.

There are several test cases.
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.

There are several test cases.
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.

5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1

1
-1

#include<iostream>
using namespace std;
const int N=1005;
const int maxint=100000000;
int map[N][N],
n;
int Dijkstra(int now,int end)
{
int used[N],dis[N];
for(int i=0;i<=n;i++)
{
dis[i]=map[now][i];
used[i]=0;
}
dis[now]=0;
used[now]=1;
for(int i=0;i<n;i++)
{
int max=maxint;
int u=now;
for(int j=0;j<=n;j++)
if(!used[j]&&dis[j]<max)
{
u=j;
max=dis[j];
}
used[u]=1;
for(int j=0;j<=n;j++)
if(!used[j]&&map[u][j]<maxint)
{
int  min=dis[u]+map[u][j];
if(min<dis[j])
{
dis[j]=min;
}
}
}
return dis[end];
}
int main ()
{
int s,e,v,m,end;
while(scanf("%d%d%d",&n,&m,&end)!=EOF)
{
for(int i=0;i<=n;i++)
for(int k=0;k<=n;k++)
map[i][k]=maxint;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&s,&e,&v);
if(map[s][e]>v)
map[s][e]=v;
}
int snum,start,ans=maxint;
scanf("%d",&snum);
for(int i=1;i<=snum;i++)
{
scanf("%d",&start);
map[0][start]=0;
}
ans=Dijkstra(0,end);
if(ans==maxint)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

3. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3