## 题目描述

Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory’s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory’s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.
Country in which Gregory traveled consists of $n$ cities and $m$ undirected roads between them. For each road Ostap knows the time it takes to travel it, and the “shortest” word above is with respect to those times.
It is guaranteed that there exists some shortest path going through all specified cities.

## 代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne = 1, top, h[N], d[N], que[N], id[N], lst[N], pre[N], ans[N];
bool in[N], v[N];
struct Edge {
int u, v, w, nxt;
} e[N << 1];

void add_edge(int u, int v, int w) {
e[++ne] = (Edge){u, v, w, h[u]}, h[u] = ne;
e[++ne] = (Edge){v, u, w, h[v]}, h[v] = ne;
}

void spfa(int s) {
int qb = 0, qe = 1;
memset(d, 0x3f, sizeof d), d[s] = 0, que[0] = s, in[s] = 1;
for (; qb != qe;) {
int u = que[qb++];
in[u] = 0, qb == N && (qb = 0);
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + e[i].w) {
d[e[i].v] = d[u] + e[i].w;
if (!in[e[i].v]) {
if (qb == qe || d[e[i].v] > d[que[qb]])
que[qe++] = e[i].v, in[e[i].v] = 1, qe == N && (qe = 0);
else
!~--qb && (qb = N - 1), que[qb] = e[i].v, in[e[i].v] = 1;
}
}
}
}

int main() {
int n, m, k, t;
scanf("%d%d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i)
scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
scanf("%d%d", &k, &t), v[t] = 1, spfa(t);
int s = t;
for (int i = 2; i <= k; ++i)
scanf("%d", &t), v[t] = 1, d[s] < d[t] && (s = t);
spfa(s);
for (int i = 1; i <= n; ++i)
id[i] = i;
std::sort(id + 1, id + n + 1, [&](int const &i, int const &j) { return d[i] < d[j]; });
for (int i : id) {
lst[i] += v[i];
for (int j = h[i]; j; j = e[j].nxt)
if (d[e[j].v] == d[i] + e[j].w && lst[e[j].v] < lst[i])
lst[e[j].v] = lst[i], pre[e[j].v] = j;
}
for (int i = 1; i <= n; ++i)
if (lst[i] == k) {
for (int j = pre[i]; j; j = pre[e[j].u])
ans[top++] = j >> 1;
break;
}
printf("%d\n", top);
for (int i = 0; i < top; ++i)
printf("%d ", ans[i]);
puts("");
return 0;
}


## 题目描述

Hurry! Two well-known software companies are recruiting programmers. Initially the total number of unemployed programmers is $n$. The companies are hiring them one by one, alternately. In one turn a company hires one of the programmers who has not been hired yet. The first company starts hiring.
Furthermore, there are some pairs of friends among the programmers. Of course, a programmer may have several friends. Friendship is a symmetrical relationship, so if $a$ is a friend of $b$ then $b$ is a friend of $a$.
All such pairs are known to the companies, and the companies follow the rule: a new programmer hired by a company must have at least one friend among the programmers already working in this company. The only exception is a programmer that a company starts with, he can be chosen arbitrarily. It may happen that after a number of turns a company can not longer hire anyone else according to the rule. In this case it stops hiring, while the other company can continue.
As usual, not all the programmers are created equal. There are three geniuses among them, and each company wants to hire as many geniuses as possible. Note that each company always can guarantee one genius to itself starting with a genius. So the question is, which company will hire two geniuses, if they both use optimal strategies.
Note that both companies have the full information during the hiring: friendship relations, who are geniuses and which programmers were hired by each company in each turn.

## 算法分析

$$\exists i, \; \forall j, \; \sum_{k=1}^3 [d_{k, i} \gt d_{k, j}] \lt 2$$

## 代码

#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne, h[N], d[3][N], que[N];
struct Edge {
int v, nxt;
} e[N << 2];

void add_edge(int u, int v) {
e[++ne] = (Edge){v, h[u]}, h[u] = ne;
e[++ne] = (Edge){u, h[v]}, h[v] = ne;
}

void get_d(int s, int *d) {
int qb = 0, qe = 1;
d[s] = 0, que[0] = s;
for (; qb < qe;) {
int u = que[qb++];
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + 1)
d[e[i].v] = d[u] + 1, que[qe++] = e[i].v;
}
}

int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0, u, v; i < m; ++i)
memset(d, 0x3f, sizeof d);
for (int i = 0; i < 3; ++i)
get_d(i, d[i]);
bool flag = 0;
for (int i = 0; !flag && i < n; ++i) {
bool ls = 1;
for (int j = 0; ls && j < n; ++j) {
int cnt = 0;
for (int k = 0; k < 3; ++k)
cnt += d[k][i] > d[k][j];
ls &= cnt < 2;
}
flag |= ls;
}
puts(flag ? "1" : "2");
return 0;
}


## 题目描述

Lily runs a repairing company that services the $Q$ blocks in the city. One day the company receives $M$ repair tasks, the $i$-th of which occurs in block $p_i$, has a deadline $t_i$ on any repairman’s arrival, which is also its starting time, and takes a single repairman $d_i$ time to finish. Repairmen work alone on all tasks and must finish one task before moving on to another. With a map of the city in hand, Lily want to know the minimum number of repairmen that have to be assign to this day’s tasks.

## 代码

#include <cstdio>
#include <cstring>

int min(int a, int b) {
return a < b ? a : b;
}

static const int Q = 25;
static const int M = 405;
int mp[Q][Q], p[M], t[M], d[M];
int nume, h[M];
struct Edge {
int v, f, nxt;
} e[M * M << 1];

void add_edge(int u, int v, int f) {
e[++ nume] = (Edge) { v, f, h[u] }, h[u] = nume;
e[++ nume] = (Edge) { u, 0, h[v] }, h[v] = nume;
}

namespace flow {
int S, T, g[M], dist[M], que[M], gap[M];

bool bfs() {
memcpy(g, h, sizeof h);
memset(dist, 0x3f, sizeof dist), memset(gap, 0, sizeof gap);
int qb = 0, qe = 1; dist[T] = 0, que[0] = T, ++ gap[0];
while (qb < qe) {
int u = que[qb ++];
for (int i = g[u]; i; i = e[i].nxt)
if (e[i ^ 1].f && dist[e[i].v] > dist[u] + 1)
dist[e[i].v] = dist[u] + 1, que[qe ++] = e[i].v, ++ gap[dist[e[i].v]];
}
return dist[S] < 1e9;
}

int dfs(int t, int low) {
if (t == T) return low;
int used = 0;
for (int &i = g[t]; i; i = e[i].nxt)
if (e[i].f && dist[e[i].v] == dist[t] - 1) {
int flow = dfs(e[i].v, min(e[i].f, low - used));
if (flow) e[i].f -= flow, e[i ^ 1].f += flow, used += flow;
if (used == low || dist[S] > T) return used;
}
if (! -- gap[dist[t]]) dist[S] = T + 1;
else ++ gap[++ dist[t]], g[t] = h[t];
return used;
}

int maxflow() {
bfs(); int flow = 0;
while (dist[S] <= T) flow += dfs(S, 1e9);
return flow;
}
}

int main() {
int q, m;
while (scanf("%d%d", &q, &m), q) {
nume = 1, memset(h, 0, sizeof h);
flow :: S = m << 1, flow :: T = (m << 1) + 1;
for (int i = 0; i < q; ++ i)
for (int j = 0; j < q; ++ j) scanf("%d", &mp[i][j]);
for (int i = 0; i < q; ++ i)
for (int j = 0; j < q; ++ j) if (! ~ mp[i][j]) mp[i][j] = 1e9;
for (int k = 0; k < q; ++ k)
for (int i = 0; i < q; ++ i)
for (int j = 0; j < q; ++ j) mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
for (int i = 0; i < m; ++ i) scanf("%d%d%d", &p[i], &t[i], &d[i]), -- p[i];
for (int i = 0; i < m; ++ i)
for (int j = 0; j < m; ++ j) if (i != j && t[i] + d[i] + mp[p[i]][p[j]] <= t[j]) add_edge(i, j + m, 1);
for (int i = 0; i < m; ++ i) add_edge(flow :: S, i, 1), add_edge(i + m, flow :: T, 1);
printf("%d\n", m - flow :: maxflow());
}
return 0;
}


## 题目描述

In the country of Never, there are $n$ cities and a well-developed road system. There is exactly one bidirectional road between every pair of cities, thus, there are as many as ${n(n – 1) \over 2}$ roads! No two roads intersect, and no road passes through intermediate cities. The art of building tunnels and bridges has been mastered by Neverians.
An independent committee has evaluated each road of Never with a positive integer called the perishability of the road. The lower the road’s perishability is, the more pleasant it is to drive through this road.
It’s the year of transport in Never. It has been decided to build a museum of transport in one of the cities, and to set a single signpost directing to some city (not necessarily the one with the museum) in each of the other cities. The signposts must satisfy the following important condition: if any Neverian living in a city without the museum starts travelling from that city following the directions of the signposts, then this person will eventually arrive in the city with the museum.
Neverians are incredibly positive-minded. If a Neverian travels by a route consisting of several roads, he considers the perishability of the route to be equal to the smallest perishability of all the roads in this route.
The government of Never has not yet decided where to build the museum, so they consider all $n$ possible options. The most important is the sum of perishabilities of the routes to the museum city from all the other cities of Never, if the travelers strictly follow the directions of the signposts. The government of Never cares about their citizens, so they want to set the signposts in a way which minimizes this sum. Help them determine the minimum possible sum for all n possible options of the city where the museum can be built.

## 代码

#include <cstdio>
#include <cstring>

#define int long long

int min(int a, int b) {
return a < b ? a : b;
}

char c; while((c = getchar()) < '0' || c > '9') ; t = c - '0';
while ((c = getchar()) >= '0' && c <= '9') (t *= 10) += c - '0';
}

static const int N = 2010;
int mp[N][N], dist[N];
bool vis[N];

signed main() {
int n, mn = 1000000001; read(n);
for (int i = 1; i < n; ++ i)
for (int j = i + 1; j <= n; ++ j) read(mp[i][j]), mn = min(mn, mp[j][i] = mp[i][j]);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j) if (i != j) mp[i][j] -= mn;
for (int i = 1; i <= n; ++ i) {
dist[i] = 1000000001;
for (int j = 1; j <= n; ++ j) if (i != j) dist[i] = min(dist[i], mp[i][j]);
dist[i] <<= 1;
}
for (int _ = n; _; -- _) {
int mn = 1000000000000000ll, p = -1;
for (int i = 1; i <= n; ++ i) if (! vis[i] && dist[i] < mn) mn = dist[p = i];
vis[p] = true;
for (int i = 1; i <= n; ++ i) dist[i] = min(dist[i], dist[p] + mp[i][p]);
}
for (int i = 1; i <= n; ++ i) printf("%lld/n", dist[i] + mn * (n - 1));
return 0;
}


## 题目描述

In the city of Dingilville the traffic is arranged in an unusual way. There are junctions and roads connecting the junctions. There is at most one road between any two different junctions. There is no road connecting a junction to itself. Travel time for a road is the same for both directions. At every junction there is a single traffic light that is either blue or purple at any moment. The color of each light alternates periodically: blue for certain duration and then purple for another duration. Traffic is permitted to travel down the road between any two junctions, if and only if the lights at both junctions are the same color at the moment of departing from one junction for the other. If a vehicle arrives at a junction just at the moment the lights switch it must consider the new colors of lights. Vehicles are allowed to wait at the junctions. You are given the city map which shows:

• the travel times for all roads (integers);
• the durations of the two colors at each junction (integers);
• and the initial color of the light and the remaining time (integer) for this color to change at each junction.

Your task is to find a path which takes the minimum time from a given source junction to a given destination junction for a vehicle when the traffic starts. In case more than one such path exists you are required to report only one of them.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct IOManager {
template <typename T>
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager operator > (T &x) {
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager operator < (T x) {
write(x); return *this;
}
} io;

struct Junction { bool c; int r, t[2]; };

struct Edge { int v, l, nxt; };

struct Solver {
private:
static const int N = 310;
static const int M = 14010;
int s, t, n, m, nume, h[N], dist[N], pre[N];
bool in[N];
Junction junc[N];
Edge e[M << 1];
void add_edge(int u, int v, int l) {
e[++ nume] = (Edge) { v, l, h[u] }, h[u] = nume;
e[++ nume] = (Edge) { u, l, h[v] }, h[v] = nume;
}
void input() {
io > s > t > n > m;
for (int i = 1; i <= n; ++ i) {
char c; io > c > junc[i].r > junc[i].t[0] > junc[i].t[1], junc[i].c = c == 'P';
}
for (int i = 1; i <= m; ++ i) {
int u, v, l; io > u > v > l, add_edge(u, v, l);
}
}
int get(int u, int v, int t) {
int cu = junc[u].c, tuu = 0, cv = junc[v].c, tvv = 0;
if (t >= junc[u].r) {
cu = ! cu; int cnt = (t - junc[u].r) / (junc[u].t[0] + junc[u].t[1]);
tuu = junc[u].r + cnt * (junc[u].t[0] + junc[u].t[1]);
if (tuu + junc[u].t[cu] <= t) tuu += junc[u].t[cu], cu = ! cu;
}
if (t >= junc[v].r) {
cv = ! cv; int cnt = (t - junc[v].r) / (junc[v].t[0] + junc[v].t[1]);
tvv = junc[v].r + cnt * (junc[v].t[0] + junc[v].t[1]);
if (tvv + junc[v].t[cv] <= t) tvv += junc[v].t[cv], cv = ! cv;
}
if (cu == cv) return t;
int cnt = 0;
while (cu != cv) {
if (cnt > 3) return 1e9;
if (tuu + (tuu ? junc[u].t[cu] : junc[u].r) < tvv + (tvv ? junc[v].t[cv] : junc[v].r)) tuu += (tuu ? junc[u].t[cu] : junc[u].r), cu = ! cu;
else if (tuu + (tuu ? junc[u].t[cu] : junc[u].r) > tvv + (tvv ? junc[v].t[cv] : junc[v].r)) tvv += (tvv ? junc[v].t[cv] : junc[v].r), cv = ! cv;
else tuu += (tuu ? junc[u].t[cu] : junc[u].r), cu = ! cu, tvv += (tvv ? junc[v].t[cv] : junc[v].r), cv = ! cv, ++ cnt;
}
return max(tuu, tvv);
}
int spfa() {
memset(dist, 0x7f, sizeof dist), dist[s] = 0;
queue <int> que; que.push(s), in[s] = true;
while (! que.empty()) {
int u = que.front(); que.pop(), in[u] = false;
for (int i = h[u]; i; i = e[i].nxt) {
int t = get(u, e[i].v, dist[u]);
if (dist[e[i].v] > t + e[i].l) {
dist[e[i].v] = t + e[i].l, pre[e[i].v] = u;
if (! in[e[i].v]) que.push(e[i].v), in[e[i].v] = true;
}
}
}
return dist[t];
}
void print(int t) {
if (! t) return;
print(pre[t]), io < t < ' ';
}
void process() {
int dis = spfa();
io < (dis < 1e9 ? dis : 0) < '\n';
if (dis < 1e9) print(t), io < '\n';
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

Pavel plays a famous computer game. A player is responsible for a whole country and he can travel there freely, complete quests and earn experience.
This country has $n$ cities connected by $m$ bidirectional roads of different lengths so that it is possible to get from any city to any other one. There are portals in $k$ of these cities. At the beginning of the game all portals are closed. When a player visits a portal city, the portal opens. Strange as it is, one can teleport from an open portal to an open one. The teleportation takes no time and that enables the player to travel quickly between rather remote regions of the country.
At the beginning of the game Pavel is in city number $1$. He wants to open all portals as quickly as possible. How much time will he need for that?

## 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
long long n, m, k, nume, tot, ans, mi = 1e18;
long long h[100001], p[100001], d[100001], fa[100001], pre[100001];
bool in[100001];
struct edge { long long v, w, nxt; } e[200001];
struct line {
long long u, v, w;
bool operator < (const line &a) const {
return d[u] + w + d[v] < d[a.u] + a.w + d[a.v];
}
} l[200001];
void add_edge(long long u, long long v, long long w) {
e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void spfa() {
queue<long long> que;
while (!que.empty()) que.pop();
for (int i = 1; i <= n; ++i)
if (!d[i]) in[i] = true, que.push(i);
while (!que.empty()) {
int u = que.front(); in[u] = false, que.pop();
for (int i = h[u]; i; i = e[i].nxt)
if (d[e[i].v] > d[u] + e[i].w) {
d[e[i].v] = d[u] + e[i].w, pre[e[i].v] = pre[u];
if (!in[e[i].v]) in[e[i].v] = true, que.push(e[i].v);
}
}
}
long long get_fa(long long t) {
return t == fa[t] ? t : fa[t] = get_fa(fa[t]);
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
long long u, v, w; cin >> u >> v >> w; add_edge(u, v, w);
}
memset(d, 0x1f, sizeof d), d[1] = 0, spfa(); cin >> k;
for (int i = 1; i <= k; ++i) {
cin >> p[i]; if (d[p[i]] < mi) mi = d[p[i]];
}
ans = mi, memset(d, 0x1f, sizeof d);
for (int i = 1; i <= n; ++i) fa[i] = i, pre[i] = i;
for (int i = 1; i <= k; ++i) d[p[i]] = 0; spfa();
for (int i = 1; i <= n; ++i)
for (int j = h[i]; j; j = e[j].nxt)
l[++tot].u = i, l[tot].v = e[j].v, l[tot].w = e[j].w;
sort(l + 1, l + tot + 1);
for (int i = 1; i <= tot; ++i) {
long long u = get_fa(pre[l[i].u]), v = get_fa(pre[l[i].v]);
if (u != v) fa[u] = v, ans += d[l[i].u] + l[i].w + d[l[i].v];
}
cout << ans << endl;
return 0;
}


## 题目描述

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.
There are n planets in their universe numbered from $1$ to $n$. Rick is in planet number $s$ (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.
By default he can not open any portal by this gun. There are $q$ plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.
Plans on the website have three types:

1. With a plan of this type you can open a portal from planet $v$ to planet $u$.
2. With a plan of this type you can open a portal from planet $v$ to any planet with index in range $[l, r]$.
3. With a plan of this type you can open a portal from any planet with index in range $[l, r]$ to planet $v$.

Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

## 代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
struct node_type {
long long l, r, child[2];
} node[2000001];
struct edge {
long long v, w, nxt;
} e[2000001];
long long n, q, s, dist[2000001], tot, nume, h[2000001];
bool in[2000001];
queue<long long> que;
void add_edge(long long u, long long v, long long w) {
if (u == v) return;
e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(long long root, int mode) {
long long mid = node[root].l + node[root].r >> 1;
if (node[root].l == mid) node[root].child[0] = node[root].l;
else {
node[++tot].l = node[root].l, node[tot].r = mid;
node[root].child[0] = tot, build_tree(tot, mode);
}
if (mid + 1 == node[root].r) node[root].child[1] = node[root].r;
else {
node[++tot].l = mid + 1, node[tot].r = node[root].r;
node[root].child[1] = tot, build_tree(tot, mode);
}
if (mode) {
} else {
}
}
void insert_line(long long root, long long l, long long r, long long v, long long w, int mode) {
if (l == node[root].l && r == node[root].r) {
return;
}
if (r < node[node[root].child[1]].l) insert_line(node[root].child[0], l, r, v, w, mode);
else if (l > node[node[root].child[0]].r) insert_line(node[root].child[1], l, r, v, w, mode);
else {
insert_line(node[root].child[0], l, node[node[root].child[0]].r, v, w, mode);
insert_line(node[root].child[1], node[node[root].child[1]].l, r, v, w, mode);
}
}
void spfa() {
memset(dist, 0x1f, sizeof(dist));
while (!que.empty()) que.pop();
que.push(s), in[s] = true, dist[s] = 0;
while (!que.empty()) {
long long t = que.front(); que.pop(); in[t] = false;
for (long long i = h[t]; i; i = e[i].nxt) {
if (dist[e[i].v] > dist[t] + e[i].w) {
dist[e[i].v] = dist[t] + e[i].w;
if (!in[e[i].v]) que.push(e[i].v), in[e[i].v] = true;
}
}
}
}
int main()
{
scanf("%lld%lld%lld", &n, &q, &s);
for (int i = 1; i <= n; ++i) {
node[i].l = node[i].r = i;
}
tot = n + 2;
node[n + 1].l = node[n + 2].l = 1;
node[n + 1].r = node[n + 2].r = n;
if (n > 1) build_tree(n + 1, 0), build_tree(n + 2, 1);
for (long long i = 1, t, v, u, l, r, w; i <= q; ++i) {
scanf("%lld", &t);
if (t == 1) {
scanf("%lld%lld%lld", &v, &u, &w);
} else {
scanf("%lld%lld%lld%lld", &v, &l, &r, &w);
insert_line(n + t - 1, l, r, v, w, t - 2);
}
}
spfa();
for (int i = 1; i <= n; ++i) {
if (dist[i] != dist[0]) printf("%lld ", dist[i]);
else printf("-1 ");
}
printf("\n");
return 0;
}


## 题目描述

ZS the Coder has drawn an undirected graph of $n$ vertices numbered from $0$ to $n-1$ and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices $s$ and $t$ in the resulting graph is exactly $L$. Can you help him?

## 代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
long long n, m, L, s, t, dist[1001], line[1001][1001];
bool flag, in[1001], sign[1001][1001];
void spfa(int p = -1, int q = -1) {
queue<int> que;
while (!que.empty()) que.pop();
memset(in, false, sizeof(in));
if (p == -1) {
memset(dist, 0x1f, sizeof(dist));
que.push(s), dist[s] = 0, in[s] = true;
} else {
if (dist[p] > dist[q]) p ^= q ^= p ^= q;
que.push(p), in[p] = true;
}
while (!que.empty()) {
long long u = que.front();
que.pop();
in[u] = false;
for (int i = 0; i < n; ++i) {
if (line[u][i] && dist[i] > dist[u] + line[u][i]) {
dist[i] = dist[u] + line[u][i];
if (!in[i]) que.push(i), in[i] = true;
}
}
}
}
int main()
{
cin >> n >> m >> L >> s >> t;
for (int i = 1; i <= m; ++i) {
long long x, y, w;
cin >> x >> y >> w;
line[x][y] = line[y][x] = w;
if (!w) sign[x][y] = sign[y][x] = true;
}
spfa();
if (dist[t] < L) {
cout << "NO" << endl;
return 0;
} else if (dist[t] > L) {
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (sign[i][j]) {
line[i][j] = line[j][i] = 1;
sign[i][j] = sign[j][i] = false;
spfa(i, j);
if (dist[t] <= L) {
line[i][j] = line[j][i] = L - dist[t] + 1;
flag = true; break;
}
}
}
if (flag) break;
}
} else flag = true;
if (!flag) cout << "NO" << endl;
else {
cout << "YES" << endl;
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (line[i][j] || sign[i][j]) {
cout << i << ' ' << j << ' ';
if (line[i][j]) cout << line[i][j];
if (sign[i][j]) cout << (long long) 1e18;
cout << endl;
}
}
}
}
return 0;
}