最短路径变型题解法举例
PAT A 1003
输入
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 1
输出
2 4
//最短路径变型题解法举例
//PAT A 1003
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//最大顶点数
const int MAXV=510;
//无穷大
const int INF=0x3fffffff;
//n为顶点数,m为边数,st和ed分别为起点和终点
//G为邻接矩阵,weight为点权
//d[]记录最短距离,w[]记录最大点权之和,num[]记录最短路径条数
int n,m,st,ed,G[MAXV][MAXV],weight[MAXV];
int d[MAXV],w[MAXV],num[MAXV];
//vis[i]==true 表示顶点i已被访问,初值均为false
bool vis[MAXV]={
false};
//s为起点
void Dijkstra(int s)
{
fill(d,d+MAXV,INF);
memset(num,0,sizeof(num));
memset(w,0,sizeof(w));
d[s]=0;
w[s]=weight[s];
num[s]=1;
//循环n次
for(int i=0;i<n;i++)
{
//u使d[u]最小,MIN存放该最小的d[u]
int u=-1;
int MIN=INF;
//找到未访问的顶点中d[]最小的
for(int j=0;j<n;j++)
{
if( vis[j]==false && d[j]<MIN )
{
u=j;
MIN=d[j];
}
}
//找不到小于INF的d[u],说明剩下的顶点和起点s不连通
if(u==-1)
{
return;
}
vis[u]=true;
for(int v=0;v<n;v++)
{
//如果v未被访问 && u能到达v && 以u为中介点可以使d[v]更优
if( vis[v]==false && G[u][v]!=INF )
{
if( d[u]+G[u][v]<d[v] )
{
//覆盖d[v]
d[v]=d[u]+G[u][v];
//覆盖w[v]
w[v]=w[u]+weight[v];
//覆盖num[v]
num[v]=num[u];
}
else if( d[u]+G[u][v]==d[v] )
{
//以u为中介点时点权之和更大
if(w[u]+weight[v]>w[v] )
{
//w[v]继承自w[u]
w[v]=w[u]+weight[v];
}
//最短路径条数与点权无关,必须写在外面
num[v]+=num[u];
}
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&ed);
for(int i=0;i<n;i++)
{
//读入点权
scanf("%d",&weight[i]);
}
int u,v;
//初始化图G
fill( G[0],G[0]+MAXV*MAXV,INF );
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
//读入边权
scanf("%d",&G[u][v]);
G[v][u]=G[u][v];
}
//Dijkstra算法入口
Dijkstra(st);
//最短距离条数,最短路径中的最大点权
printf("%d %d\n",num[ed],w[ed]);
return 0;
}