传送门:P9751 [CSP-J 2023] 旅游巴士
为了那个梦我们扬帆起航,为了理所到来的那天跨越无尽黑夜
由于这几天做的题目太少,我用小号立下flag:
导致果然做了一晚上。。。。
并且最后还是没做出来被我妈强制去睡觉了
题目意思:
题目很明白了,这里说几个要注意的点:
- 道路均只能单向通行
- 到达和离开景区的时间都必须是 \(k\) 的非负整数倍:说明在景区里呆着的时间也要是 \(k\) 的非负整数倍,即路径长度是 \(k\) 的非负整数倍
- 对于每条道路均设置了一个开放时间 \(a_i\),游客只有不早于 \(a_i\) 时刻才能通过这条道路:说明 起始时间+到达这个点的路径长度要 \(\ge a_i\)
思路:一档档地想
1st:不存在合法方案
输出 “-1”,拿到 5 pts
2nd:考虑 \(a_i = 0\),\(k = 1\)
直接求从起点到终点的最短路径长度。
SPFA,启动!
#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,k;//先考虑 k = 1,a[i] = 0 的情况
const int maxn=10100;
const int maxm=20100;
int en;
int fir[maxn];
struct edge{
int v,next;
}ed[maxm];
void add_edge(int u,int v)
{
en++;
ed[en].v=v;
ed[en].next=fir[u];
fir[u]=en;
}
queue<int>q;
int dist[maxn];
bool inque[maxn];
void SPFA(int r)
{
for(int i=1;i<=n;i++)
{
dist[i]=LLONG_MAX;
}
dist[r]=0;
q.push(r);
inque[r]=true;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=fir[now];i;i=ed[i].next)
{
int p=ed[i].v;
if(dist[now]+1<dist[p])
{
dist[p]=dist[now]+1;
if(!inque[p]){
q.push(p);
inque[p]=true;
}
}
}
}
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int u,v,t;
cin>>u>>v>>t;
add_edge(u,v);
}
if(k==1){
SPFA(1);
if(dist[n]==LLONG_MAX) cout<<-1<<endl;
else cout<<dist[n]<<endl;
}
else cout<<-1<<endl;
return 0;
}
分值:15pts
3rd:只考虑 \(k \le 1\) 的情况。
如果在搜索最短路的时候,出现到了一条路的开放时间大于当前最短路,即从 \(0\) 时刻出发,到达这个点早了。我们就晚一点出发。
因为每走一条路,需要的时间是 \(1\),晚 \(1\) 时刻出发,就能晚 \(1\) 时刻到达这个节点,想要在道路开放的时候恰好到达这里,就要晚出发 \(a_i\)(到达 \(p\) 点的路径的开放时间) \(- dist_{now}\)(现在所处的时间点) ,即 \(dist_p\) (要到达的点所用的时间) \(= min\) \(\{dist_p,dist_{now} + 1 + a_i - dist_{now}\}\) \(= min\) \(\{dist_p,1 + a_i\}\)
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,k;//先考虑 k = 1,a[i] = 0 的情况
const int maxn=10100;
const int maxm=20100;
int en;
int fir[maxn];
struct edge{
int v,next;
int d;
}ed[maxm];
void add_edge(int u,int v,int t)
{
en++;
ed[en].v=v;
ed[en].d=t;
ed[en].next=fir[u];
fir[u]=en;
}
queue<int>q;
int dist[maxn];
bool inque[maxn];
void SPFA(int r)
{
for(int i=1;i<=n;i++)
{
dist[i]=LLONG_MAX;
}
dist[r]=0;
q.push(r);
inque[r]=true;
while(!q.empty())
{
int now=q.front();
inque[now]=false;
q.pop();
for(int i=fir[now];i;i=ed[i].next)
{
int p=ed[i].v;
int t=ed[i].d;
if(t>dist[now])
{
if(t+1<dist[p])//1+t
{
dist[p]=t+1;
if(!inque[p]){
q.push(p);
inque[p]=true;
}
}
}
else if(dist[now]+1<dist[p]){
dist[p]=dist[now]+1;
if(!inque[p]){
q.push(p);
inque[p]=true;
}
}
}
}
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int u,v,t;
cin>>u>>v>>t;
add_edge(u,v,t);
}
if(k<=1){
SPFA(1);
if(dist[n]==LLONG_MAX) cout<<-1<<endl;
else cout<<dist[n]<<endl;
}
else cout<<-1<<endl;
return 0;
}
分值:30pts
Finally:考虑把 \(k\) 加进去
虽然好像考试拿到上面的分就能差不多 \(1=\) 了(山东去年 1= 线是 190)
但是还是要做出这道题来啊!!!
首先,这部分我一开始是不会的,参考了洛谷上很多大佬的题解
上面我们已经说过:
如果在搜索最短路的时候,出现到了一条路的开放时间大于当前最短路,即从 \(0\) 时刻出发,到达这个点早了。我们就晚 \(k\) 的倍数出发。
即:如果现在的时间是 \(t\),这条路的开放时间是 \(a_i\),\(a_i > t\),那么我们可以在现在这个点等待 \(k\) 的倍数的时间直到可以通行。
具体等待的时间 \(w\) 为:\(\lceil \frac{a_i - t}{k} \rceil \times k\),即到达这条边的终点所用的时间为 \(t+w\)
我们可以建立状态:定义 \(dis_{i,j}\) 为到达 \(i\) 号点的时间 \(\bmod k\) 的值为 \(j\) 时的最短消耗时间。
那么答案显然是 \(dis_{n,0}\)
考虑转移:
- 如果 \(t \ge a_i\) 了,那么可以直接通过,则 \(dist_{v,(t+1) \bmod k} \to \min(dist_{v,(t+1) \bmod k},t+1)\)。
- 否则令 \(w=\lceil \frac{a_i-t}{k} \rceil \times k+t\),即我们在入口处等待一些时间,使得可以走到这条边,转移为 \(dist_{v,(w+1) \bmod k} \to \min(dist_{v,(w+1) \bmod k},w+1)\)。
这是一个图上的 DP,我们可以使用 SPFA 的方法更新。即枚举每条遍历到的边 \((u,v,w)\),如果 \(dist_u\) 更新了 \(dist_v\),那么继续遍历 \(v\) 的出边并更新。
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=10100;
const int maxm=20100;
const int maxk=105;
int n,m,k;
int en;
int fir[maxn];
struct edge{
int v,a;
int next;
}ed[maxm];
inline int read()
{
int f=1,x=0;char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
void add_edge(int u,int v,int a)
{
en++;
ed[en].a=a,ed[en].v=v;
ed[en].next=fir[u];
fir[u]=en;
}
int dist[maxn][maxk];
queue<pair<int,int> >q;
bool inque[maxn][maxk];
void spfa(int p)
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
dist[i][j]=LLONG_MAX;
}
}
dist[p][0]=0;
q.push({p,0});
inque[p][0]=true;
while(!q.empty())
{
int now=q.front().first;
int kkk=q.front().second;
q.pop();
inque[now][kkk]=false;
int t=dist[now][kkk];
for(int i=fir[now];i;i=ed[i].next)
{
int v=ed[i].v;
int a=ed[i].a;
if(t>=a){
if(dist[v][(t+1)%k]>t+1)
{
dist[v][(t+1)%k]=t+1;
if(!inque[v][(t+1)%k])
{
q.push({v,(t+1)%k});
inque[v][(t+1)%k]=true;
}
}
}
else{
int w=((a-t+k-1)/k)*k+t;
if(dist[v][(w+1)%k]>w+1)
{
dist[v][(w+1)%k]=w+1;
if(!inque[v][(w+1)%k])
{
q.push({v,(w+1)%k});
inque[v][(w+1)%k]=true;
}
}
}
}
}
}
signed main()
{
n=read(),m=read(),k=read();
//cin>>n>>m>>k;
for(int i=1;i<=m;i++)
{
int u,v,a;
u=read(),v=read(),a=read();
//cin>>u>>v>>a;
add_edge(u,v,a);
}
spfa(1);
if(dist[n][0]==LLONG_MAX) cout<<-1<<endl;
else cout<<dist[n][0]<<endl;
return 0;
}
后记:
好难的一道题啊。。。我太弱了qwq
离正解就差了一个 DP。。加上一维就AC啦!
鬼知道这东西出来的时候我有多开心。。
希望csp_j 2024 rp++ !!!
最优解第六页寄!(SPFA怎么你了)我看谁还说它s了,它可救过我的命啊
要没有它我说不定就 AFO 了 TAT