JZOJ3501 | 物语(ものがたり)

Cover Image
[00:19.90] その日眺めていた光景は
[00:23.69] 映く青い空が染んでいて
[00:27.70] 不意にカランとした教室に
[00:31.02]
[00:31.73] 君はもういなかった
[00:34.95]
[00:35.65] 昨日読めなかった小説を
[00:39.17]
[00:39.70] 消えない夢を見ていた少年は
[00:43.63] 赤く光る星を追っていた
[00:47.08]
[00:47.60] それの1つになりたかった
[00:50.92] いつも触れ合えば願うこと
[00:55.20] もどかしい言葉が窓を使う
[00:59.12] 最終の電車の窓に映り込む
[01:03.28] 自分は誰に見える
[01:07.79] ああ青春のありかは
[01:10.64] こんなにいるの
[01:12.60] 見つかてないから
[01:14.69] 今日で何でだって
[01:16.50] 落ちた移れだって
[01:18.61] 探してるんだろう
[01:20.59] 探してるんだろう
[01:22.30]
[01:24.74] 少年の僕らは
[01:26.72] 情熱な君が
[01:28.70] 約束のまま
[01:30.51] 消えてしまうなら
[01:32.47] 過ぎ去ってしまうなら
[01:34.56] ここに残そう
[01:37.59] 思い世界にだけだったの
[01:41.06]
[01:55.99] 道の向こうには自分がいて
[01:59.15]
[01:59.69] あどけない笑顔で呼んでいる
[02:03.60] きっと先に辿り着いたんだ
[02:07.10]
[02:07.63] 消えないうちに行かなくちゃ
[02:11.34] 気づかになれば痛むほど
[02:15.30] 進むべき志士が強く浮かぶ
[02:19.08] 始まりの合図に
[02:21.03] この音が鳴る
[02:23.14] 変わらないいつのままで
[02:27.52]
[02:28.71] 最初は誰かのものばかりの
[02:32.50] まだ先にあるから
[02:34.59] 祈る音の価値を
[02:36.71] 幼い心の前
[02:38.56] 過ぎててるだろう
[02:40.74] 続けてるだろう
[02:42.19]
[02:44.70] 少年の僕らは
[02:46.55] 暖かいな日々は
[02:48.62] ずっとこれから
[02:50.60] 二人の奥で
[02:52.61] 心の底で
[02:54.56] いつか輝く
[02:57.77] 君はもう気づいてるんだろう
[03:01.07]
[03:15.83] 不安と消えないと恐怖
[03:17.93] 乗り着いてて
[03:19.60] 躊躇いまま羽ばたくんだ
[03:23.42] 自然とその場所が理由になるんで
[03:27.62] 誰よりも期待してる
[03:30.47]
[03:32.63] 少年の僕らは
[03:34.62] 心の中に戸惑いがあるなら
[03:38.52] きっとそれ次第だ
[03:40.68] きっとこの世界で
[03:42.85] 口は綺麗で
[03:44.45] 眩しい思いだろう
[03:46.86]
[03:48.68] 青春の絵から
[03:50.58] その一ページの
[03:52.53] そのさり気なく
[03:54.56] 君を選んで
[03:56.63] 泣きそうな声で
[03:58.56] そっと呟く
[04:01.69] 同じ世界に向かってだと
[04:05.03]
[04:09.82] 同じ未来に勝ってるだと

* 虽然题目背景是《六兆年と一夜物语》但是我就是要放占戈哥欠。


Portal (Please contact zsjz1934@163.com)

目前应该只有中山纪念中学 OJ 有这道题,所以先放一下题面。

问题描述
  某一天,少年邂逅了同病相连的 IA。见面后,IA 一把牵起少年的手,决定和他一起逃离部落,离开这个无法容身的是非之地。
  要逃离部落,少年和 IA 就需要先选择一条耗时最少的路线,从而避免被部落的大人们抓到。部落可以大致分为 NN 个区域,少年和 IA 在区域 11,部落的出口设在区域 NN。此外部落还有 MM 条连接两个区域道路。道路是无向的,没有一条道路的两端连接相同的区域,也没有两条道路所连接的两个区域完全相同。对于其中前 M1M-1 条道路,其通过时间是确定的,但最后一条道路,由于地理因素,通过其的时间会不断变化。
  现在,少年和 IA 得知了在 KK 个不同的时段里,通过第 MM 条道路的时间,请您分别计
算出在这 KK 个时段中逃离部落的最少时间,以帮助他们确定行动的时刻。
输入格式
  第一行三个整数 N,M,KN,M,K,分别表示区域数,道路数,询问数。接下来 M1M-1 行每行三个整数 ui,vi,wi(uivi,1ui,viN,0<wi109)u_i,v_i,w_i(u_i\neq v_i,1\leq u_i,v_i\leq N,0<w_i\leq 10^9),表示这条道路连接的区域和通过时间。紧接着是两个整数 ui,vi(uivi,1ui,viN)u_i,v_i(u_i\neq v_i,1\leq u_i,v_i\leq N),表示第 MM 条道路连接的区域。最后 KK 行,每行一个正整数 xi(0<xi109)x_i(0<x_i\leq 10^9),表示目前第 MM 条道路的通过时间。
输出格式
  输出共计 KK 行,每行一个整数,表示对应时段逃离部落的最短时间。如果在该时段内无法逃离,输出 +Inf
HINT
  对于 100% 的数据,N2×105,M5×105,K3×104N\leq 2\times 10^5,M\leq 5\times 10^5,K\leq 3\times 10^4

题目给了一张有 V=N|V|=N 个顶点 E=M|E|=M 条边没有重边没有自环的无向图 G(V,E)G(V,E)。设第 MM 条边为 ex,ye_{x,y} 起点终点为 u,vu,v,则答案为以下三种路径中最短的:

  • uvu\rightarrow v
  • uxyvu\rightarrow x\rightarrow y\rightarrow v
  • uyxvu\rightarrow y\rightarrow x\rightarrow v

所以只要对 uvu\rightarrow vuxu\rightarrow xvyv\rightarrow yuyu\rightarrow yvxv\rightarrow x 跑 Dijkstra 再 O(1)O(1) 回答即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
Reiwa-flavored code
*/
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
typedef long long ll;
typedef std::pair<ll, int> pli;
const int N = 2e5 + 1, M = 1e6 + 1;
ll ans, oo = 5e14, dis[2][N];
int n, m, k, it, hed[N], nxt[M], ver[M], edg[M];
int read() {
int x = 0, c = getchar();
while(c < 48 || c > 57) c = getchar();
while(c > 47 && c < 58) {x = x * 10 + c - 48; c = getchar();}
return x;
}
void link(int u,int v,int w) {
ver[++it] = v; edg[it] = w; nxt[it] = hed[u]; hed[u] = it;
ver[++it] = u; edg[it] = w; nxt[it] = hed[v]; hed[v] = it;
}
void dijkstra(int s, int p) {
int u, vis[N] = {};
for(int i = 1; i <= n; ++i) dis[p][i] = oo;
dis[p][s] = 0;
std::priority_queue<pli> heap; heap.push((pli){0,s});
while(heap.size()) {
u = heap.top().second; heap.pop();
if(vis[u]) continue; vis[u]=1;
for(int i = hed[u], v, w; i; i = nxt[i]) {
v = ver[i]; w = edg[i];
if(dis[p][u] + w < dis[p][v])
dis[p][v] = dis[p][u] + w, heap.push((pli){-dis[p][v], v});
}
}
}
int main() {
n = read(), m = read(), k = read();
for(int i = 1, u, v, w; i < m; ++i)
u = read(), v = read(), w = read(), link(u, v, w);
int x = read(), y = read();
dijkstra(1, 0);
dijkstra(n, 1);
for(int i = 0, w; i < k; ++i) {
w = read();ans = dis[0][n];
ans = std::min(ans, dis[0][x] + w + dis[1][y]);
ans = std::min(ans, dis[0][y] + w + dis[1][x]);
if(ans < oo) printf("%lld\n", ans); else puts("+Inf");
}
return 0;
}

Download

写得很丑,#15N=1×105,M=5×105,K=3×104N=1\times 10^5,M=5\times 10^5,K=3\times 10^4)几乎要 T 掉。两年前就做过这题,不过题解咕到现在。

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。