程序设计天梯赛L2-1 (pta经典最短路题目)

题目 题意: 给定n个点、m条边的图，求从st到ed的最短路。记录最短路的路径，如果最短路不止一条，则记录点权和最大的那一条，题目保证该路径唯一。另，输出最短路路径的数量。 思路: Dijkstra，额外维护几个数组即可。 如果dist[j] > dist[u] + w, cnt[j] = cnt[u]. (因为j由u转移过来) 如果dist[j] == dist[u] + w,cnt[j] += cnt[u] (因为j多了从u来的路) 另外，相等时需要判断是否点权和更大，依此来更新。 时间复杂度: O(mlogm) 代码:

#include
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 502;
struct node{
	int v;
	int w;
	node()
	{
		
	}
	node(int a,int b)
	{
		v = a,w = b;
	}
};
vector va[N];
int a[N];
int n,m,k,T;
int st,ed;
int pre[N];
int dist[N];
bool vis[N];
int cnt[N];
int sum[N];
void Dij(int st)
{
	memset(dist,0x3f,sizeof(dist));
	priority_queue q;
	q.push({0,st});
	cnt[st] = 1;
	sum[st] = a[st];
	dist[st] = 0;
	while(q.size())
	{
		PII tmp = q.top(); q.pop();
		int u = tmp.second;
//		cout