题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805489282433024
题意
一个无向图,有N个节点,有N-1个(自行车)站点,编号为0的点时自行车总部PBMC,每个站点可容纳的自行车数最大是Cmax,边的权值Tij表示序号ij两站之间需要花费的时间,
对于一个站点,如果自行车数为零或者满了,都属于问题车站,现给出图中一个问题车站序号Sp,求出总部到Sp的最短路径(时间最短),并且使得途径的每一个站的自行车数都
变得完美(即自行车数都为Cmax/2)。当有多条最短路时,找到使得总部需要发出自行车数最少的路径。
Sample Input:
10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1
Sample Output:
3 0->2->3 0
思路:
求最短路用Dijkstra,并且记录每个节点的上一个路径信息(可能有多个)。
注意遍历最优路径树的写法(只需一个temp空间,参考柳神的写法)
ps:Dijkstra访问的下一个点:必须是未被访问过的点中d值最小的,即最近的点。
code
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct node{
int C;//当前车数
int d;//距离
int id;//节点序号
}station[505];
bool operator < (const node &x,const node &y) {return x.d>y.d;}
struct side{
int to;//指向哪个节点
int T;//权
side(int a,int b):to(a),T(b){}
};
vector<side>G[505];
int Cmax,N,Sp,M;
int flag[505];//标记访问
vector<int>fa[505];//保存路径树
void dij()
{
for(int i=1;i<=N;++i) station[i].d=inf;
station[0].d=0; station[0].id=0;
priority_queue<node>Q;//默认大顶堆
Q.push(station[0]);
while(!Q.empty())
{
node temp=Q.top(); Q.pop();
if(flag[temp.id]) continue;
flag[temp.id]=1;//标记
//对from节点进行relax
int from=temp.id;
for(int i=0;i<G[temp.id].size();++i) {
int to=G[temp.id][i].to;
if(flag[to]==0) {//没标记过
if(station[to].d>station[from].d+G[temp.id][i].T){
station[to].d=station[from].d+G[temp.id][i].T;
fa[to].clear();
fa[to].push_back(from);
}
else if(station[to].d==station[from].d+G[temp.id][i].T) {
fa[to].push_back(from);
}
Q.push(station[to]);
}
}
}
}
int min_send=inf;
int _now=0;
vector<int> ans,temp;
void path(int x)
{
temp.push_back(x);
if(x==0) {//结束标记,检查该路径
int minn=0,sum=0;
for(int i=temp.size()-2;i>=0;--i)
{
sum+=station[temp[i]].C-Cmax/2;
minn=min(sum,minn);
}
minn=-minn;
if(minn<min_send) {
min_send=minn;
ans.clear();
ans=temp;
_now=sum+minn;
}
}
for(int i=0;i<fa[x].size();++i) {
path(fa[x][i]);
}
temp.pop_back();
}
int main()
{
cin>>Cmax>>N>>Sp>>M;
for(int i=1;i<=N;++i) cin>>station[i].C,station[i].id=i;
for(int i=1;i<=M;++i)
{
int a,b,c;
cin>>a>>b>>c;
G[a].push_back(side(b,c));
G[b].push_back(side(a,c));
}
dij();//最短路算法,按结点前驱保存路径
path(Sp);//深搜遍历所有路径,找出符合要求的路径保存下来(ans)
cout<<min_send<<" ";
for(int i=ans.size()-1;i>=0;--i) {
cout<<ans[i];
if(i>0) cout<<"->";
}
cout<<" "<<_now<<endl;
return 0;
}