你到底在为谁等待,无人内心潮澎湃
2026-10-24 17:11:36
发布于:浙江
最短路主题。
代码给的是不同时候的(我写这些题的时候),可能会有不同的写法,如存图方式,存边的写法等,但均为本人代码,见谅。
纽约的月纽约的夜 纽约的背包客一个人坐在街对面
注意到题目让我们转换数据。
那就写一个函数,也就是本题代码里的 来转换借口,是每条边都是能被完美对接的,那么这道题目就变成了一个简单的最短路问题。
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace syh;
typedef long long ll;
const ll inf=1e18;
int n, m;
vector<pair<ll,int>> g[200005];
ll dis[200005];
int cl(int t)//t的反口
{
return (t>n?t-n:t+n);
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int u, v;
ll w;
cin>>u>>v>>w;
g[u].push_back({w,cl(v)});//连反口
g[v].push_back({w,cl(u)});
}
int s, t;
cin>>s>>t;
s=cl(s);//处理起点变成反口
for(int i = 1;i<=2*n;i++) dis[i]=inf;
dis[s]=0;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
q.push({0,s});
while(!q.empty())
{
auto cur=q.top();
q.pop();
ll d=cur.first;
int u=cur.second;
if(dis[u]<d) continue;
for(auto e:g[u])
{
ll w=e.first;
int v=e.second;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
if(dis[t]==inf) cout<<"I have no idea how to solve it.";
else cout<<dis[t];//能接上
}
我在武侯区,被我耍成了 Malibu
这道题就是一个类似于回路一样的东西,去显然是直接跑最短路,但是返回的时候如果在每个点跑一次显然时间会炸,于是我们使用一个图存一个相反的单向边,比如说 1→2→5,对应着真正图的 5→2→1,因为所有的边都是反向的,所以这个图也叫反图。
显然有了这个反图只需要在这个图上跑一次最短路就可以知道多个节点到 的距离。
#include <iostream>
#include <vector>
#include <climits>
#include <queue>
using namespace syh;
typedef long long ll;
const ll inf=1e18;
const int maxn=1000005;
vector<pair<int,int>> g[maxn];
vector<pair<int,int>> rg[maxn];
ll dis[maxn];
int n, m;
void dij(int s,vector<pair<int,int>> g[])
{
for(int i = 1;i<=n;i++) dis[i]=inf;
dis[s]=0;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>> h;
h.emplace(0,s);
while(!h.empty())
{
ll d=h.top().first;
int u=h.top().second;
h.pop();
if(d>dis[u]) continue;
for(auto &e:g[u])
{
int v=e.first;
int w=e.second;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
h.emplace(dis[v],v);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll ans=0;
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
g[u].emplace_back(v,w);
rg[v].emplace_back(u,w);
}
dij(1,g);
for(int i = 2;i<=n;i++) ans+=dis[i];
dij(1,rg);
for(int i = 2;i<=n;i++) ans+=dis[i];
cout<<ans;
}
拿三条A 通杀牌 打东南西北中发白
也是个反图题目,我们求完来回的最短路后从节点 开始累加即可。
#include <iostream>
#include <queue>
#include <vector>
using namespace syh;
const int inf=1e9;
int n, m;
long long dis1[1005], dis2[1005];
vector<pair<int,int>> g[1005];
vector<pair<int,int>> rg[1005];
void dijkstra(vector<pair<int,int>> gr[],long long dis[],int s)
{
for(int i = 1;i<=n;i++) dis[i]=inf;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({0,s});
dis[s]=0;
while(!q.empty())
{
auto cur=q.top();
q.pop();
int d=cur.first, u=cur.second;
if(dis[u]<d) continue;
for(auto &e:gr[u])
{
int w=e.first, v=e.second;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
g[u].push_back({w,v});
rg[v].push_back({w,u});
}
dijkstra(g,dis1,1);
dijkstra(rg,dis2,1);
long long ans=0;
for(int i = 2;i<=n;i++) ans=ans+dis1[i]+dis2[i];
cout<<ans;
}
Me and my bro 我们全部都坐进了 DD backseat
我们都知道最短路使用的是优先队列的小根堆,那么求最长路只要每次队列顶部是堆里的最大值即可,使用 priority_queue 大根堆来解决。
#include <iostream>
#include <vector>
#include <queue>
using namespace syh;
const long long inf=1e18;
vector<pair<int,int>> g[50005];
long long dis[50005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin>>n>>m;
for(int i = 1;i<=n;i++) dis[i]=-inf;
dis[1]=0;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
g[u].emplace_back(v,w);
}
priority_queue<pair<long long,int>,vector<pair<long long,int>>> h;
h.emplace(0,1);
while(!h.empty())
{
long long d=h.top().first;
int u=h.top().second;
h.pop();
if(d<dis[u]) continue;
for(auto &e:g[u])
{
int v=e.first;
int w=e.second;
if(dis[v]<dis[u]+w&&dis[u]!=-inf)
{
dis[v]=dis[u]+w;
h.emplace(dis[v],v);
}
}
}
if(dis[n]!=-inf) cout<<dis[n];
else cout<<-1;
}
喧哗的影像片 播了半天得想该怎么引领她
最板的一题了吧。
注意建双向边去跑最短路,记得初始化。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace syh;
const int inf=1e9;
vector<pair<int,int>> g[200005];
int main()
{
int n, m, dis[2550];
cin>>n>>m;
for(int i = 1;i<=n;i++) dis[i]=inf;
for(int i = 1;i<=m;i++)
{
int u, v, w;
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({1,0});
dis[1]=0;
while(!q.empty())
{
auto cur=q.top();
q.pop();
int u=cur.first, d=cur.second;
if(d>dis[u]) continue;
for(auto e:g[u])
{
int v=e.first;
int w=e.second;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push({v,dis[v]});
}
}
}
cout<<dis[n];
}
同行对手 rapstar 被我搞得很凉 没了我他们保准黄
富有新意的板子。
其实就是在线的给你的图加上几条边,这几条边在后面跑最短路的时候也可以用,所以不要预处理,直接在线跑就行。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace syh;
const int inf=1e9;
vector<pair<int,int>> g[5005];
int n, m, dis[105];
void dij(int s,int t)
{
for(int i = 1;i<=n;i++) dis[i]=inf;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({s,0});
dis[s]=0;
while(!q.empty())
{
auto cur=q.top();
q.pop();
int u=cur.first, d=cur.second;
if(d>dis[u]) continue;
for(auto e:g[u])
{
int v=e.first, w=e.second;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push({v,dis[v]});
}
}
}
if(dis[t]==inf) cout<<"-1\n";
else cout<<dis[t]<<'\n';
}
int main()
{
cin>>n>>m;
while(m--)
{
int op;
cin>>op;
if(op==0)
{
int s, t;
cin>>s>>t;
dij(s,t);
}
else
{
int u, v, w;
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
}
}
任凭那狂风吹散了我 繁花到残朵隐入土坡
P2912 [USACO08OCT] Pasture Walking G
Floyd 板题。
跑完 Floyd 后对于每次查询输出 dis[s][t] 即可。
#include <iostream>
using namespace syh;
const int inf=1e9;
int dis[1005][1005], n, q;
void floyd()
{
for(int k = 1;k<=n;k++)
{
for(int i = 1;i<=n;i++)
{
if(dis[i][k]==inf) continue;
for(int j = 1;j<=n;j++)
{
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>q;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
dis[i][j]=inf;
}
dis[i][i]=0;
}
for(int i = 1;i<n;i++)
{
int u, v, w;
cin>>u>>v>>w;
dis[u][v]=w;
dis[v][u]=w;
}
floyd();
while(q--)
{
int s, t;
cin>>s>>t;
cout<<dis[s][t]<<'\n';
}
}
I have a colt 45 Wouldn't tell a lie
P2951 [USACO09OPEN] Hide and Seek S
你说的对,但是这题真的是板子啊。
对于最后的一些处理,我们可以枚举 dis[i] 来确定最长的最短路是到哪个节点的,再通过这些 dis[i] 值找到有多少条这样的路即可。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace syh;
const int inf=1e9;
int n, m, dis[50005];
vector<pair<int,int>> g[50005];
int main()
{
cin>>n>>m;
for(int i = 1;i<=n;i++) dis[i]=inf;
for(int i = 1;i<=m;i++)
{
int a, b;
cin>>a>>b;
g[a].push_back({b,1});
g[b].push_back({a,1});
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push({0,1});
dis[1]=0;
while(!q.empty())
{
auto cur=q.top();
q.pop();
int d=cur.first, u=cur.second;
if(d>dis[u]) continue;
for(auto e:g[u])
{
int v=e.first, w=e.second;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
int ans=0, cnt=0;
for(int i = 1;i<=n;i++) ans=max(ans,dis[i]);
for(int i = 1;i<=n;i++)//满足输出最小的
{
if(dis[i]==ans)
{
cout<<i<<" ";
break;
}
}
for(int i = 1;i<=n;i++)
{
if(dis[i]==ans) cnt++;
}
cout<<ans<<' '<<cnt;
}
明日我若走以后 东边为我升太阳
模拟 Floyd 的过程。
我们只需保证现在的 值不会超过当前时间即可,最后可以通过判断时间是否超出或者最短路是否成功建立来输出 -1 的答案。
#include <iostream>
using namespace syh;
const int inf=1e9;
int n, m, q, dis[205][205], t[205];
int main()
{
cin>>n>>m;
for(int i = 0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
dis[i][j]=inf;
}
dis[i][i]=0;
}
for(int i = 0;i<n;i++) cin>>t[i];
for(int i = 0;i<m;i++)
{
int u, v, w;
cin>>u>>v>>w;
dis[u][v]=w;
dis[v][u]=w;
}
cin>>q;
int ptr=0;//现在作为k的村庄
while(q--)
{
int x, y, ti;
cin>>x>>y>>ti;
while(ptr<n&&t[ptr]<=ti)
{
int k=ptr;
for(int i = 0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
if(dis[i][k]!=inf&&dis[k][j]!=inf)
{
int road=min(dis[i][j],dis[i][k]+dis[k][j]);
dis[i][j]=road;
}
}
}
ptr++;
}
if(t[x]>ti||t[y]>ti||dis[x][y]==inf) cout<<"-1\n";
else cout<<dis[x][y]<<'\n';
}
}
用祝福做最后的对白 搬空的房间是感情的遗址
这里可以用一个 cnt 数组来计数,如果可以更新最短路,那么这里的最短路数量就等于接上这个现节点的节点的最短路数量(长难句),如果当前的节点 的最短路长度等于取出的节点 连到 的长度,那么这里的最短路数量就是两个节点的 cnt 值加起来的和再取模。
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace syh;
const int mod=100003;
const int maxn=1e6+5;
vector<int> g[maxn];
int n, m, dis[maxn], cnt[maxn];
int main()
{
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int x, y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
memset(dis,0x3f,sizeof dis);
queue<int> q;
dis[1]=0;
cnt[1]=1;
q.push(1);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v:g[u])
{
if(dis[u]+1<dis[v])
{
dis[v]=dis[u]+1;
cnt[v]=cnt[u];
q.push(v);
}
else if(dis[u]+1==dis[v])
{
cnt[v]=(cnt[v]+cnt[u])%mod;
}
}
}
for(int i = 1;i<=n;i++) cout<<cnt[i]<<'\n';
}
犹豫了一辈子的承诺也无法兑现 荒诞无稽的回忆慢慢碎成碎片
一道二分 最短路,二分大家都知道要二分最大值,不过 函数里的东西我们可以这样写。
首先跑最短路,不过这里要注意如果一条路的边权超过这个二分出的最大值了,那么我们就舍弃,最后判断一下这个二分值能否满足最短路到节点 血量(也就是 dis[n]) 即可判别这个二分出的答案是否合法。
#include <iostream>
#include <vector>
#include <queue>
using namespace syh;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n, m;
ll b, f[10005], l=inf, r, ans;
vector<pair<int,ll>> g[10005];//邻接表,pair<v,边权c>
bool check(ll mid)
{
if(f[1]>mid||f[n]>mid) return false;//起点终点必须能走
vector<ll> dis(n+1,inf);
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;//无负边权用dijkstra
dis[1]=0;
q.emplace(0,1);
while(!q.empty())
{
pair<ll,int> cur=q.top();
q.pop();
ll d=cur.first;
int u=cur.second;
if(d>dis[u]) continue;//不是最短路就不要
for(auto &edg:g[u])
{
int v=edg.first;
ll c=edg.second;
if(f[v]>mid) continue;//超过最大值不让走
if(dis[v]>d+c)
{
dis[v]=d+c;//更新最短路
q.emplace(dis[v],v);
}
}
}
return dis[n]<=b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
ans=-1;
cin>>n>>m>>b;
for(int i = 1;i<=n;i++)
{
cin>>f[i];
l=min(l,f[i]);
r=max(r,f[i]);
}
for(int i = 1;i<=m;i++)
{
int a, b;
ll c;
cin>>a>>b>>c;
//双向边
g[a].emplace_back(b,c);
g[b].emplace_back(a,c);
}
while(l<=r)//二分答案
{
ll mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(ans==-1) cout<<"AFK";
else cout<<ans;
}
做点不太顶满的音乐你带情感的听 希望平缓下你那时常敏感的心
可以建立分层图来跑最短路,最后枚举这几层图里的最小 dis[t] 值就行。
#include <iostream>
#include <queue>
using namespace syh;
const int inf=1e9;
const int maxn=11*1e5;
struct edge
{
int to, d, nxt;
}ed[50005*50];
struct node
{
int v, w;
bool operator<(const node &b) const
{
return w>b.w;
}
};
priority_queue<node> q;
int n, m, k, s, t, cnt0, dis[maxn], head[maxn];
void add(int u,int v,int w)
{
ed[++cnt0].to=v;
ed[cnt0].d=w;
ed[cnt0].nxt=head[u];
head[u]=cnt0;
}
void dij()
{
for(int i = 0;i<=maxn;i++) dis[i]=inf;
dis[s]=0;
q.emplace(s,0);
while(!q.empty())
{
auto cur=q.top();
q.pop();
int u=cur.v;
int d=cur.w;
if(d>dis[u]) continue;
for(int i = head[u];i;i=ed[i].nxt)
{
int v=ed[i].to;
int w=ed[i].d;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.emplace(v,dis[v]);
}
}
}
}
int main()
{
cin>>n>>m>>k>>s>>t;
for(int i = 1;i<=m;i++)
{
int a, b, c;
cin>>a>>b>>c;
for(int j = 0;j<=k;j++)
{
add(a+j*n,b+j*n,c);
add(b+j*n,a+j*n,c);
add(a+j*n,b+(j+1)*n,0);//上去一层免费
add(b+j*n,a+(j+1)*n,0);//上去一层免费
}
}
dij();
int ans=inf;
for(int i = 0;i<=k;i++) ans=min(ans,dis[t+i*n]);
cout<<ans;
}
从我成年那天我就想住进上海 因为我家客厅里面有张光盘
我们可以求出最少所需要的边数,这样用总边数减去它就得到了答案。
这里有些小细节,一个是不能有不能到的路(这里指两个节点不相通),一个是花费的最短时间不能超,在编代码的时候要注意一下。
算节点 到两个城市的最短路在加上由节点 到节点 的最短路就是节点 到两个城市的最短路。
//由于有些边不能重复算,所以我们可以算1-i、s1-i、s2-i的最短路,边数之和就是总需要边数,答案为总边数-最少需要边数
#include <iostream>
#include <vector>
#include <queue>
using namespace syh;
const int INF=1e9;//定义极值更新最小需要边数
int n, m;
int s1, t1, s2, t2;
vector<int> g[3005];
int dis1[3005], dis_s1[3005], dis_s2[3005];//三个数组存最短路
void bfs(int st,int dis[])
{
for(int i = 1;i<=n;i++) dis[i]=-1;//都初始化避免答案错误
queue<int> qu;
dis[st]=0;
qu.push(st);
while(!qu.empty())
{
int u=qu.front();
qu.pop();
for(int v:g[u])
{
if(dis[v]==-1)
{
dis[v]=dis[u]+1;
qu.push(v);
}
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int x, y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
cin>>s1>>t1>>s2>>t2;
//两次反向BFS分别跑最短路(因为起点不知道)
bfs(1,dis1);
bfs(s1,dis_s1);
bfs(s2,dis_s2);
int minn=INF;
for(int i = 1;i<=n;i++)
{
if(dis1[i]==-1||dis_s1[i]==-1||dis_s2[i]==-1) continue;//不能有不可达的路
if(dis1[i]+dis_s1[i]<=t1&&dis1[i]+dis_s2[i]<=t2)//判断条件是否符合
{
minn=min(minn,dis1[i]+dis_s1[i]+dis_s2[i]);//更新最小的答案
}
}
cout<<m-minn;//总边数减最少需要边数
}
反向可以正确实现的原因是边的长度仍然是不变的。
Ayo Everybody 欢迎翻开我的记事簿 早听烂了三部曲那现在连载第四部
注意一个点被进入的时间其实是到达它的时间与它的所有发生器被打掉的时间的较大值,所以我们用拓扑排序的思想建立 in 数组记录入边,直到这个值为 这个城市才能被解锁加入优先队列,注意这里也要用到建反图的思想,因为我们要等一个节点被攻占时更新与它相关联的城市的发生器数量。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace syh;
typedef long long ll;
const ll inf=1e18;
struct edge
{
int v;
ll w;
};
int n, m;
vector<vector<edge>> g;
vector<vector<int>> v;//反图
vector<int> in;
vector<ll> dis, lim;
int main()
{
cin>>n>>m;
g.resize(n+1);
v.resize(n+1);
in.resize(n+1);
dis.assign(n+1,inf);
lim.assign(n+1,0);
for(int i = 0;i<m;i++)
{
int u, v;
ll w;
cin>>u>>v>>w;
g[u].push_back({v,w});
}
for(int x=1;x<=n;x++)
{
int l;
cin>>l;
in[x]=l;
for(int j = 0;j<l;j++)
{
int p;
cin>>p;
v[p].push_back(x);
}
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
dis[1]=0;
q.push({max(dis[1],lim[1]),1});
while(!q.empty())
{
auto [tiu,u]=q.top();
q.pop();
if(tiu>max(dis[u],lim[u])) continue;
for(auto &e:g[u])
{
int v=e.v;
ll w=e.w;
if(dis[v]>tiu+w)
{
dis[v]=tiu+w;
if(in[v]==0)//要等城市被解锁才能加入优先队列
{
q.push({max(dis[v],lim[v]),v});
}
}
}
for(int x:v[u])//因为u被攻陷了所以要更新一下u对应的每个城市的in值
{
lim[x]=max(lim[x],tiu);//比到最晚的攻占时间
if(--in[x]==0) q.push({max(dis[x],lim[x]),x});//把城市x也放进优先队列里
}
}
cout<<max(dis[n],lim[n]);
}
全部评论 4
- 置顶
可能要退一段时间OI了,希望大家在CSP能拿到好的分数,等你们的喜报
1周前 来自 浙江
1为什么啊
1周前 来自 广东
0被父母压力了,说没有强基没有OI,我们期中考试就分强基了,所以到11月中期大概不会再搞
1周前 来自 浙江
1/咦
1周前 来自 广东
0
高质不火(严肃看不懂)
1周前 来自 浙江
0d
1周前 来自 浙江
08黄5绿1青
1周前 来自 浙江
0





















有帮助,赞一个