【日常训练】Volleyball（CodeForces-96D）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意与分析

这题也是傻逼题，可是我当时打比赛的时候板子出问题了- -|||，怎么调也调不过。

不过思路是很清晰的：先做n次dijkstra然后重新建图，建完了以后根据新的单向图再跑一次dijkstra。

代码

#include <bits/stdc++.h> #define ZERO(x) memset(x, 0, sizeof(x))
using namespace std;
using ll=long long; struct Edge { int v, nxt; ll c; };
Edge w[];
vector<int> que;
ll dist[], a[], b[];
int e[][], ww[];
bool vis[];
int N, M, x, y, W = ; void ShortestPath(int s)
{
memset(dist, , sizeof(dist)); dist[s] = ;
ZERO(vis); vis[s]=true;
que.clear();
que.push_back(s);
for (int fi = ; fi < que.size(); ++ fi)
{
int u = que[fi];
for (int i = ww[u]; i; i = w[i].nxt)
{
int v = w[i].v;
if (dist[v] <= dist[u] + w[i].c) continue;
dist[v] = dist[u] + w[i].c;
if (vis[v]) continue;
vis[v] = true;
que.push_back(v);
}
vis[u] = false;
} e[s][] = ;
for (int i = ; i <= N; ++ i)
if (i != s && dist[i] <= a[s]) e[s][++ e[s][]] = i;
} int main()
{
cin >> N >> M;
cin >> x >> y;
for (int i = , u, v; i <= M; ++ i)
{
ll c;
cin >> u >> v >> c;
w[++ W].v = v; w[W].c = c; w[W].nxt = ww[u]; ww[u] = W;
w[++ W].v = u; w[W].c = c; w[W].nxt = ww[v]; ww[v] = W;
}
for (int i = ; i <= N; ++ i) cin >> a[i] >> b[i];
for (int i = ; i <= N; ++ i) ShortestPath(i); memset(dist, , sizeof(dist)); dist[x] = ;
ZERO(vis); vis[x]=true;
que.clear();
que.push_back(x);
for (int fi = ; fi < que.size(); ++ fi)
{
int u = que[fi];
for (int i = ; i <= e[u][]; ++ i)
{
int v = e[u][i];
if (dist[v] <= dist[u] + b[u]) continue;
dist[v] = dist[u] + b[u];
if (vis[v]) continue;
vis[v] = ;
que.push_back(v);
}
vis[u] = ;
} if (dist[y] > (1ll << )) dist[y] = -;
cout << dist[y] << endl; return ;
}