PAT 1003 Emergency
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Input
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) - the number of cities (and the cities are numbered from 0 to N-1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
Output
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
Sample Input
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1Sample Output
2 4一、Dijkstra 已通过<span style="font-size:14px;">#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int CITYNUM = 500;
const int INF = 0x7fffffff;
int city[CITYNUM]; //记录各个城市的团队数
int road[CITYNUM][CITYNUM]={0};
bool visited[CITYNUM]={false};
int minLen[CITYNUM]={0}; //从源城市到达index城市的最短路径值 全部初始化为0
int sum[CITYNUM]={0}; //从源城市到达index城市，所能召集的最大团队数
int same[CITYNUM]={0}; //从源城市到达index城市,具有相同最短的路径个数
void Dij(int source,int dest,int n){ //dijkstra算法
int i,t,min,next;
int count = 0; //已确定最短路径的城市数量
int cur = source;
sum[cur]=city[cur]; //团队数量初始化
same[cur]=1; //相同最短路径数量初始化
while(count< n-1){ //依次确定到n-1个城市的最短路径
visited[cur]=true;
min=INF;// 离源城市距离的最小值
for(i=0;i<n;i++){ //对城市cur的所有出边进行拓展
if(visited[i])
continue;
if(road[cur][i]){
t = minLen[cur] + road[cur][i];
if(t < minLen[i] || minLen[i]==0){ //到达城市i，出现新的最短路径
minLen[i]=t;
same[i]=same[cur]; //到达城市i与到达城市cur的路径相同
sum[i]=sum[cur]+city[i];
}else if(t == minLen[i]){ //到达城市i，出现相同的最短路径
same[i]+=same[cur]; //到达城市i的路径多出来一条主干分支
if(sum[cur]+city[i] > sum[i]) //记下团队数较大的值
sum[i]=sum[cur]+city[i];
}
}
if(minLen[i] < min && minLen[i]!=0){ //在n个城市中，选出一个离源城市最近的城市
min = minLen[i]; //到达城市i的最短路径
next = i; //下一次while循环将以该城市i为中心进行拓展
}//for循环结束后选择的结果是城市cur，因为基于贪心算法，cur与cur的距离为0，最小
}
minLen[cur] = min;//从源城市到达cur城市的最短路径值
if(next == dest)//到达终点
break;
cur = next; //到达城市next的最短路径已经确定，下一步将对城市next的所有出边进行松弛
count++; //确定最短路径的城市加一
}
return;
}
int main()
{
int n,m,sc,dc;
cin>>n>>m>>sc>>dc;
int i;
for(i=0;i<n;i++)
cin>>city[i];
int c1,c2;
for(i=0;i<m;i++){
cin>>c1>>c2;
cin>>road[c1][c2];
road[c2][c1]=road[c1][c2];
}
if(sc==dc){ //若所在地就是目的地 则直接输出结果
cout<<1<<' '<<city[sc]<<endl;
return 0;
}
Dij(sc,dc,n);
cout<<same[dc]<<' '<<sum[dc]<<endl;
return 0;
}
</span>
二、写的floyd算法 一直无法通过，不知问题出哪里了
<span style="font-size:14px;">#include<iostream>
#define max 500 //城市数量最大值
#define INT_MAX 214748364
using namespace std;
int teams[max];
int path[max][max];// path[i][j] 用来记录从城市j回溯城市i的第一个中转城市
int e[max][max];
int main()
{
int n,m,c1,c2,rs=0;// n:城市数量 M:道路数量 C1:城市1 C2:城市2 rs:最终集结救援队的人数
int cnt=0; //求最短路径的个数
int minPath;//最短路径的长度
cin>>n>>m>>c1>>c2;
int i,j,k,len;
for(i=0;i<n;i++)
{
cin>>teams[i];//城市i的救援队数量
}
//初始化
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
{
e[i][j]=0;
}
else
{
e[i][j]=INT_MAX;
}
}
}
for(i=0;i<m;i++)
{
cin>>j>>k>>len;//道路i 从城市j 至城市k 距离为len
e[j][k]=len;
}
//回溯路径 初始化
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
{
path[i][j]=-1;//城市i到城市i的上一条路径为空，用-1表示
}else if(e[i][j]!=0&&e[i][j]!=INT_MAX){
path[i][j]=i;
}
else
{
path[i][j]=INT_MAX; //城市i到城市j 不可达
}
}
}
for(k=0;k<n;k++)
{
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
if(i!=j&&k!=i&&k!=j&&e[i][j]>=e[i][k]+e[k][j])//路径相同时，将城市k作为中转，可以召集城市k的救援队
{
e[i][j]=e[i][k]+e[k][j];
path[i][j]=k;//从城市j回溯城市i的第一个中转城市
}
}
}
}
//最短路径回溯，求得能集结的最多救援队
rs=teams[c2];
int node1,node2;
node1=c1;
node2=c2;
while(path[node1][node2]!=-1){
int prefix =path[node1][node2];
rs+=teams[prefix];
node2=prefix;
}
//求最短路径的个数
minPath=e[c1][c2];//最短路径的长度
for(k=0;k<n;k++)
{
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
if(e[i][j]>=e[i][k]+e[k][j])
{
e[i][j]=e[i][k]+e[k][j];
if(i==c1&&j==c2&&minPath==e[i][j]&&k!=c2){
cnt++;
//cout<<i<<"->"<<j<<"的中转站是："<<k<<endl;
}
}
}
}
}
cout<<cnt<<" "<<rs<<endl;
return 0;
}
</span>