题目地址:https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840
题目:
解题思路:
dijkstra
num[i]表示到结点i的最短路径条数
sum[i]表示到结点i的(最短路径中)能召集的最多救援队数量
当在更新最短路的时候遇到:(以u为中介,s->u+u->v==s->v)
dis[v] == dis[u] + edges[u][v]
最短路径的条数为num[u]+num[v],如果peo[v]+sum[u]>sum[v]则更新sum[v]
ac代码:
dijkstra中循环n次(不直接初始化dis[i])推荐这样写,代码量少,更简单
#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define maxn 505
typedef long long ll;
const ll inf=99999999;
using namespace std;
ll dis[maxn],edges[maxn][maxn],pre[maxn],peo[maxn],vis[maxn]={0},sum[maxn]={0},num[maxn]={0};
ll n,m,s,d,a,b,c;
vector<ll> ans;
void solve()
{
edges[s][s]=0;dis[s]=0;
sum[s]=peo[s],num[s]=1;
for(int j=0;j<n;j++)
{
ll min = inf - 1, u = -1;
for (ll i = 0; i < n; i++)
{
if (dis[i] < min && !vis[i])
{
min = dis[i];
u = i;
}
}
if(u==-1) return ;//不连通
vis[u] = 1;
for (ll v = 0; v < n; v++)
{
if(!vis[v]&&edges[u][v]!=inf)
{
if (dis[v] > dis[u] + edges[u][v])
{
dis[v] = dis[u] + edges[u][v];
pre[v] = u;
sum[v] = peo[v] + sum[u];//更新获取的救援队的数目
num[v] = num[u];//更新到达i最短路的条数
} else if (dis[v] == dis[u] + edges[u][v])
{
num[v] += num[u];//更新条数
if (peo[v] + sum[u] > sum[v])//更新后的sum[i]>原sum[i]
{
sum[v] = peo[v] + sum[u];
pre[v] = u;
}
}
}
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%lld %lld %lld %lld",&n,&m,&s,&d);
fill(edges[0],edges[0]+maxn*maxn,inf);
fill(dis,dis+maxn,inf);
for(ll i=0;i<n;i++)
scanf("%lld",&peo[i]);
for(ll i=0;i<m;i++)
{
scanf("%lld %lld %lld",&a,&b,&c);
edges[a][b]=edges[b][a]=c;
}
solve();
ll x=d;
while(x!=s)
{
ans.push_back(x);
x=pre[x];
}
ans.push_back(s);
printf("%lld %lld\n",num[d],sum[d]);
for(int i=ans.size()-1;i>=0;i--)
{
if(i!=ans.size()-1)
printf(" ");
printf("%lld",ans[i]);
}
return 0;
}
dijkstra中循环n-1次(dis[i]的初始化放在dijkstra的外面写)
#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define maxn 505
typedef long long ll;
const ll inf=99999999;
using namespace std;
ll dis[maxn],edges[maxn][maxn],pre[maxn],peo[maxn],vis[maxn]={0},sum[maxn]={0},num[maxn]={0};
ll n,m,s,d,a,b,c;
vector<ll> ans;
void solve()
{
for(int j=1;j<n;j++)
{
ll min = inf - 1, u = -1;
for (ll i = 0; i < n; i++)
{
if (dis[i] < min && !vis[i])
{
min = dis[i];
u = i;
}
}
if(u==-1) return ;//不连通
vis[u] = 1;
for (ll v = 0; v < n; v++)
{
if(!vis[v]&&edges[u][v]!=inf)
{
if (dis[v] > dis[u] + edges[u][v])
{
dis[v] = dis[u] + edges[u][v];
pre[v] = u;
sum[v] = peo[v] + sum[u];//更新获取的救援队的数目
num[v] = num[u];//更新到达i最短路的条数
} else if (dis[v] == dis[u] + edges[u][v])
{
num[v] += num[u];//更新条数
if (peo[v] + sum[u] > sum[v])//更新后的sum[i]>原sum[i]
{
sum[v] = peo[v] + sum[u];
pre[v] = u;
}
}
}
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%lld %lld %lld %lld",&n,&m,&s,&d);
fill(edges[0],edges[0]+maxn*maxn,inf);
fill(dis,dis+maxn,inf);
for(ll i=0;i<n;i++)
scanf("%lld",&peo[i]);
for(ll i=0;i<m;i++)
{
scanf("%lld %lld %lld",&a,&b,&c);
edges[a][b]=edges[b][a]=c;
}
edges[s][s]=0;dis[s]=0;
sum[s]=peo[s],num[s]=1;
vis[s]=1;
for(int i=0;i<n;i++)
if(edges[s][i]!=inf&&i!=s)
{
dis[i]=edges[s][i];
pre[i]=s;
num[i]=num[s];
sum[i]=sum[s]+peo[i];
}
solve();
ll x=d;
while(x!=s)
{
ans.push_back(x);
x=pre[x];
}
ans.push_back(s);
printf("%lld %lld\n",num[d],sum[d]);
for(int i=ans.size()-1;i>=0;i--)
{
if(i!=ans.size()-1)
printf(" ");
printf("%lld",ans[i]);
}
return 0;
}