当前位置：首页 > news >正文

NOIP2025模拟赛15

news 2025/11/2 21:04:08

T1	T2	T3	T4
\({\color{#FFC116} 普及/提高− }\)	\({\color{#3498DB} 提高+/省选− }\)	\({\color{#9D3DCF} 省选/NOI− }\)	\({\color{#9D3DCF} 省选/NOI− }\)

参赛网址：https://oj.33dai.cn/d/TYOI/contest/688ab0fd1cb63c9e03c923bc

T2,T3,T4搭建未完成

T1 出租车[2022NOIP模拟赛T1(合并DIV)]

题目传送门

题目难度：\({\color{#FFC116} 普及/提高− }\)

算法标签：图结构，最短路

思路

考虑将图重构，首先跑一边全员最短路，确定 \(i\) 可以到达的其他点，然后连接 \(i\) 到 \(j\)，权值为 \(c_i\)。再跑最短路即可。

时间复杂度 \(O(n^2\times\log_2n)\)

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=2005;
const int inf=1e18;
int T;
int n,m,s,t;
struct edge{int u,w;friend bool operator < (const edge x,const edge y){return x.w>y.w;}
};
struct taxi{int t,c;
}a[maxn];
int dis[maxn],dist[maxn][maxn];
priority_queue<edge> Q;
vector<edge> G[maxn],e[maxn];void dij(int s){for (int i=1;i<=n;i++)	dist[s][i]=inf;dist[s][s]=0;Q.push({s,0});while (Q.size()>0){edge t=Q.top();Q.pop();int u=t.u;for (int i=0;i<(int)G[u].size();i++){int v=G[u][i].u;int w=G[u][i].w;if (dist[s][v]>dist[s][u]+w){dist[s][v]=dist[s][u]+w;Q.push({v,dist[s][v]});}}}
}void dij1(int s){for (int i=1;i<=n;i++)	dis[i]=inf;dis[s]=0;Q.push({s,0});while (Q.size()>0){edge t=Q.top();Q.pop();int u=t.u;for (int i=0;i<(int)e[u].size();i++){int v=e[u][i].u;int w=e[u][i].w;if (dis[v]>dis[u]+w){dis[v]=dis[u]+w;Q.push({v,dis[v]});}}}
}signed main(){ios::sync_with_stdio(false);cin.tie(0);
//	freopen("taxi.in","r",stdin);cin>>T;while (T--){cin>>n>>m;cin>>s>>t;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});}for (int i=1;i<=n;i++)	dij(i);for (int i=1;i<=n;i++)	cin>>a[i].t>>a[i].c;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (i==j)	continue;if (a[i].t<dist[i][j])	continue;e[i].push_back({j,a[i].c});}}dij1(s);if (dis[t]==inf)	dis[t]=-1;cout<<dis[t]<<"\n";for (int i=1;i<=n;i++)	G[i].clear(),e[i].clear();}return 0;	
}