最短路径变型题解法举例

题解法举例"/>

最短路径变型题解法举例

最短路径变型题解法举例

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;
}