近期一次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"

去掉就可以。