# Nemlit 的博客

By a konjac

### 题解 P5590 【赛车游戏】

posted on 2019-10-13 23:31:01 | under 题解 |

## $Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define _ 20005
struct edge {
int u, v, w, next;
}e1[_], e2[_], e3[_ << 1];
il void add1(int u, int v) {
}
il void add2(int u, int v) {
}
il void dfs1(int u) {
v1[u] = 1;
for(re int i = head1[u]; i; i = e1[i].next) if(!v1[e1[i].v]) dfs1(e1[i].v);
}
il void dfs2(int u) {
v2[u] = 1;
for(re int i = head2[u]; i; i = e2[i].next) if(!v2[e2[i].v]) dfs2(e2[i].v);
}
queue<int>q;
il void SPFA() {
memset(dis, -64, sizeof(dis)), q.push(1), dis[1] = 0;
while(!q.empty()) {
int u = q.front(); q.pop(), vis[u] = 0;
for(re int i = head3[u]; i; i = e3[i].next) {
int v = e3[i].v;
if(dis[v] < dis[u] + e3[i].w) {
dis[v] = dis[u] + e3[i].w;
if(!vis[v]) q.push(v), vis[v] = 1, ++ num[v];
if(num[v] > n) puts("-1"), exit(0);
}
}
}
}
int main() {
rep(i, 1, m) {
}
dfs1(1), dfs2(n), cnt = 0;
if(!v1[n]) return puts("-1"), 0;
rep(i, 1, n) if(v1[i] && v2[i]) pax[i] = 1;
rep(i, 1, m) if(pax[e1[i].u] && pax[e1[i].v]) add2(e1[i].u, e1[i].v);
SPFA(), printf("%d %d\n", n, m);
rep(i, 1, m) {
if(pax[e1[i].u] && pax[e1[i].v]) {
printf("%d %d %d\n", e1[i].u, e1[i].v, dis[e1[i].v] - dis[e1[i].u]);
}
else printf("%d %d %d\n", e1[i].u, e1[i].v, 9);
}
return 0;
}