题目链接:PTA-紧急救援
题意:
n点,m边的无向图,每个点有一个点权,求从st到ed的最短路条数,并输出点权和最大的一条最短路,输出权值和路径。
题解:
更新点权时类似于最短路更新。
参考代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 600;
const int MAXM = 500 * 500;
const int inf = 0x3f3f3f3f;
int n, m, st, ed;
int val[MAXN], ans[MAXN];
struct EDGE
{
int v, w, nxt;
} edge[MAXM];
int cnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].nxt = fir[u];
fir[u] = cnt++;
}
struct node
{
int u;
int d;
node(int u, int d) : u(u), d(d) {}
bool operator<(const node &a) const
{
return d > a.d;
}
};
bool used[MAXN];
int dis[MAXN], CNT[MAXN], pre[MAXN];
void dijkstra(int st)
{
priority_queue<node> que;
while (!que.empty())
que.pop();
memset(dis, inf, sizeof(dis));
memset(CNT, 0, sizeof(CNT));
memset(pre, -1, sizeof(pre));
dis[st] = 0;
CNT[st] = 1;
ans[st] = val[st];
que.push(node(st, dis[st]));
memset(used, 0, sizeof(used));
while (!que.empty())
{
int u = que.top().u;
que.pop();
if (used[u])
continue;
used[u] = 1;
for (int i = fir[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
int w = edge[i].w;
if (used[v])
continue;
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
CNT[v] = CNT[u];
ans[v] = ans[u] + val[v];
pre[v]=u;
que.push(node(v, dis[v]));
}
else if (dis[v] == dis[u] + w)
{
CNT[v] += CNT[u]; //记录最短路数
if(ans[v]<ans[u]+val[v])
{
ans[v]=ans[u]+val[v];
pre[v]=u;
}
}
}
}
}
int main()
{
scanf("%d%d%d%d", &n, &m, &st, &ed);
memset(fir, -1, sizeof(fir));
for (int i = 0; i < n; i++)
scanf("%d", &val[i]);
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
}
dijkstra(st);
printf("%d %d\n", CNT[ed], ans[ed]);
int temp=ed;
vector<int> a;
a.clear();
while(pre[temp]!=-1)
{
a.push_back(temp);
temp=pre[temp];
}
a.push_back(st);
for(int i=a.size()-1;i>0;i--)
printf("%d ",a[i]);
printf("%d",a[0]);
return 0;
}