GESP 8 T2
2026-09-17 06:29:48
发布于：浙江
32阅读
0回复
0点赞
做完了。
1 而且我还问了豆包。
本来想写 spfa 结果写完被T飞了，后面甚至用了手写的queue，最后用的反图预处理才过。
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace syh;
struct node
{
int v, l, t;
};
const int INF=1e9;
int n, m, q, l[505][505], r[505][505], arv[505];
vector<node> g[1005];
int cl[505], cr[505];
void dij(int st)
{
for(int i = 1;i<=n;i++)
{
cl[i]=INF;
cr[i]=-1;
arv[i]=0;
}
priority_queue<pair<int,int>> q;
cl[st]=0;
cr[st]=INF;
q.push({cr[st],st});
while(!q.empty())
{
auto s=q.top();
q.pop();
int d=s.first, u=s.second;
int lu=cl[u];
if(d<cr[u]) continue;
if(lu>d) continue;
for(auto &e:g[u])
{
int v=e.v;
int l=e.l;
int t=e.t;
int nr=min(d,l-arv[u]);
int nl=lu;
if(nl>nr) continue;
if(nr>cr[v])
{
cl[v]=nl;
cr[v]=nr;
arv[v]=arv[u]+t;
q.push({cr[v],v});
}
}
}
for(int i = 1;i<=n;i++)
{
l[st][i]=cl[i];
r[st][i]=cr[i];
}
}
int main()
{
cin>>n>>m>>q;
for(int i = 1;i<=m;i++)
{
int u, v, l, t;
cin>>u>>v>>l>>t;
g[u].push_back({v,l,t});
}
for(int i = 1;i<=n;i++) dij(i);
while(q--)
{
int x, y, s;
cin>>x>>y>>s;
if(l[x][y]<=s&&r[x][y]>=s) cout<<"Yes\n";
else cout<<"No\n";
}
}
#include <iostream>
#include <vector>
using namespace syh;
struct node
{
int v, l, t;
};
const int INF=1e9;
int n, m, q;
vector<node> g[1005];
int dis[505];
bool inq[505];
int qu[505*505];
int head, tail;
void solve()
{
int x, y, s;
cin>>x>>y>>s;
if(x==y)
{
cout<<"Yes\n";
return;
}
for(int i = 1;i<=n;i++)
{
dis[i]=INF;
inq[i]=false;
}
dis[x]=s;
head=0;
tail=0;
qu[tail++]=x;
inq[x]=true;
while(head<tail)
{
int u=qu[head++];
inq[u]=false;
if(dis[u]>=dis[y]) continue;
for(auto &e:g[u])
{
if(dis[u]<=e.l)
{
int nd=dis[u]+e.t;
if(nd<dis[e.v])
{
dis[e.v]=nd;
if(!inq[e.v])
{
inq[e.v]=true;
qu[tail++]=e.v;
}
}
}
}
}
if(dis[y]!=INF) cout<<"Yes\n";
else cout<<"No\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>q;
for(int i = 1;i<=m;i++)
{
int u, v, l, t;
cin>>u>>v>>l>>t;
g[u].push_back({v,l,t});
}
while(q--)
{
solve();
}
}
AC CODE
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace syh;
struct node
{
int v, l, t;
};
const int INF=1e9;
int n, m, q;
vector<node> g[1005];
vector<node> rg[1005];
int bes[505][505];
void yu(int st)
{
vector<int> late(n+1,-INF);
vector<bool> d(n+1,false);
late[st]=INF;
priority_queue<pair<int,int>> q;
q.push({INF,st});
while(!q.empty())
{
auto [val,u]=q.top();
q.pop();
if(d[u]) continue;
if(val!=late[u]) continue;
d[u]=true;
for(auto &e:rg[u])
{
int v=e.v;
int l=e.l;
int t=e.t;
if(min(l,late[u]-t)>late[v])
{
late[v]=min(l,late[u]-t);
q.push({min(l,late[u]-t),v});
}
}
}
for(int i = 1;i<=n;i++) bes[st][i]=late[i];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>q;
for(int i = 1;i<=m;i++)
{
int u, v, l, t;
cin>>u>>v>>l>>t;
g[u].push_back({v,l,t});
rg[v].push_back({u,l,t});
}
for(int i = 1;i<=n;i++) yu(i);
while(q--)
{
int x, y, s;
cin>>x>>y>>s;
if(x==y)
{
cout<<"Yes\n";
continue;
}
if(bes[y][x]>=s) cout<<"Yes\n";
else cout<<"No\n";
}
}
总而言之这是道图论初步的好题。
有帮助，赞一个