最近一次pat考试中的最后一题。其实玩算法这东西就像打魔兽，不能光有思想上的高度，微操必须实打实。就这么个迪杰斯特拉算法，多少教科书上都讲烂了。但是现场又有多少人是敲对的呢？不能光停留在理解上，必须能用自己的方式表达出来才算过关。

题目:

1087. All Roads Lead to Rome (30)

6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1

3 3 195 97
HZH->PRS->ROM

题目的意思很明确，给定图的点和边，起点，终点，求最短路径并且打印。如果有相同的情况，判断总的幸福指数，如果还是相同，判断平均幸福指数。本题唯一的难点就在于统计相同路径的条数。

我们用数组存储到达每个点的相同路径的条数，初始值都是1。

实际上就只有两种情况，第一：这个点A被其他点B更新了，那么到达A的相同的最短路径条数就是B点的相同最短路径条数。

第二：起点到A点和B点的长度相等，那么A点的最短路径条数就是A本身的条数加上B点的条数。

// pat-1087.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

#include"algorithm"
#include"map"
#include"vector"
#include"string"
#include"iostream"
#include"stack"
using namespace std;

#define max 300
#define inf 2100000000//!!!
int dis[max][max]={0};
int n=0;
int visited[max]={0};
int father[max]={0};
int same[max]={0};
int happies[max]={0};
int finalhappies[max]={0};
int precnt[max]={0};
map<int,string> cityname;
map<string,int> citynum;
stack<string> ans;
void dijstrak(int s)
{  
	same[0]=1;
	visited[s]=1;
	for(int i=0;i<n;i++)
	{
		 int min=inf;
		 int mark=-1;
	     for(int j=0;j<n;j++)
		 {//find min
		     if(visited[j]==0&&dis[s][j]<min)
			 {
			    min=dis[s][j];
			    mark=j;
			 }
		 }
		 if(mark==-1)
			 return ;
		 visited[mark]=1;//marked
		 for(int k=0;k<n;k++)
		 {//updata
			 if(visited[k]==1)
				 continue;
			 int raw=dis[s][k];
			 int another=dis[s][mark]+dis[mark][k];
		    if(raw>another)
			{   same[k]=same[mark];
		        dis[s][k]=dis[s][mark]+dis[mark][k];
				father[k]=mark;
				finalhappies[k]=finalhappies[mark]+happies[k];
				precnt[k]=precnt[mark]+1;
			}
			else if(raw==another)
			{
				same[k]+=same[mark];
				if(finalhappies[k]<finalhappies[mark]+happies[k])
				{
					father[k]=mark;
					finalhappies[k]=finalhappies[mark]+happies[k];
					precnt[k]=precnt[mark]+1;
				}
				else if(finalhappies[k]==finalhappies[mark]+happies[k])
				{
				   if(precnt[k]>(precnt[mark]+1))
				   {
					   father[k]=mark;
					   precnt[k]=precnt[mark]+1;
				   }
				}
			}

			}
				
		 }
	}

int main()
{
	for(int i=0;i<max;i++)
	    for(int j=0;j<max;j++){
			dis[i][j]=inf;
			dis[j][i]=inf;
			dis[i][i]=inf;
			dis[j][j]=inf;
	}
   int k=0;
   string s;
   cin>>n>>k>>s;
   cityname[0]=s;
   string citystr;
   int happy=0;
   for(int i=1;i<n;i++)
   {
	cin>>citystr>>happy;
	cityname[i]=citystr;
	citynum[citystr]=i;
	happies[i]=happy;
	finalhappies[i]=happy;
	precnt[i]=1;
	same[i]=1;
   }
   string city1,city2;
   int cost=0;
   for(int i=0;i<k;i++){
     cin>>city1>>city2>>cost;
	 int j=citynum[city1];
	 int b=citynum[city2];
	 dis[j][b]=cost;
	 dis[b][j]=cost;
   }

   dijstrak(0);   

   int romanum=citynum["ROM"];
   int index=romanum;
   string path;
   path+=s;//"HZH"
   ans.push("ROM");
   while(father[index]!=0)
   {
	 string pathcity=cityname[father[index]];
	 ans.push(pathcity);
	 index=father[index];
   }
   while(!ans.empty()){
	   path+="->";
	   path+=ans.top();
	   ans.pop();
   }
   cout<<same[romanum]<<" "<<dis[0][romanum]<<" "<<finalhappies[romanum]<<" "<<finalhappies[romanum]/precnt[romanum]<<endl;
   cout<<path<<endl;
  return 0;
}

#include "stdafx.h"

pat-1087【最短路径】