CodeForces 360E Levko and Game(Codeforces Round #210 (Div. 1))

题意:有一些无向边m条权值是给定的k条权值在[l,r]区间可以由你来定,一个点s1 出发一个从s2出发  问s1 出发的能不能先打到f

思路:最短路。

首先检测能不能赢 在更新的时候  如果对于一条边 a->b  如果dis1[a] <dis2[a]  那么选择这条边就选择   l  因为这条边对于s1有利 如果两个起点都选择了这条边  则说明s1 赢定了,所以要让他们尽量走这条,所以边权越小越好。跑完之后检测 如果  dis1[f]<dis2[f] 那么 就赢了。

接下来判断能不能平局。因为目前已经没有赢的可能了  那么  把dis1[a]<dis2[a]改成dis1[a]<=dis2[a] 选择l  其他选择r 即可。原因:小于的话毫无疑问就是选择l  ;等于的话选择小的如果两个都走了这条边则平局。

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include <iostream>
#include<vector>
#include<queue>
#define INF 1e15
#define LL long long
#define P pair<LL,int>
#define MP make_pair
#define M 200000
#define N 100000
using namespace std;
priority_queue<P> q;
struct node {
int l, r, to, nx;
} e[M];
int head[N];
int ecnt;
int ans[N];
void addedge(int x, int y, int l, int r) {
e[ecnt].l = l;
e[ecnt].r = r;
e[ecnt].to = y;
e[ecnt].nx = head[x];
head[x] = ecnt++;
}
LL d1[N], d2[N];
int n, m, k, s1, s2, f;
void gao(int bo) {
while (!q.empty())
q.pop();
memset(ans, -, sizeof(ans));
for (int i = ; i <= n; ++i)
d1[i] = d2[i] = INF;
d1[s1] = d2[s2] = ;
q.push(MP(, s1));
q.push(MP(, s2));
while (!q.empty()) {
P ee = q.top();
q.pop();
LL va = -ee.first;
int id = ee.second;
if (va > d1[id] && va > d2[id])
continue;
bool ok;
if (bo == ) {
if (d1[id] < d2[id])
ok = true;
else
ok = false;
} else {
if (d1[id] <= d2[id])
ok = true;
else
ok = false;
}
for (int i = head[id]; i != -; i = e[i].nx) {
int u = e[i].to;
LL add;
if (ok)
add = e[i].l;
else
add = e[i].r;
ans[i] = add;
if (d1[u] > d1[id] + add) {
d1[u] = d1[id] + add;
q.push(MP(-d1[u], u));
}
if (d2[u] > d2[id] + add) {
d2[u] = d2[id] + add;
q.push(MP(-d2[u], u));
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
scanf("%d%d%d", &s1, &s2, &f);
memset(head, -, sizeof(head));
ecnt = ;
for (int i = ; i < m; ++i) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
addedge(x, y, z, z);
}
for (int i = ; i < k; ++i) {
int x, y, l, r;
scanf("%d%d%d%d", &x, &y, &l, &r);
addedge(x, y, l, r);
}
gao();
if (d1[f] < d2[f]) {
puts("WIN");
for (int i = m; i < m + k; ++i) {
if (ans[i] == -)
ans[i] = e[i].l;
printf("%d", ans[i]);
if (i == m + k - )
puts("");
else
printf(" ");
}
return ;
}
gao();
if (d1[f] == d2[f]) {
puts("DRAW");
for (int i = m; i < m + k; ++i) {
if (ans[i] == -)
ans[i] = e[i].l;
printf("%d", ans[i]);
if (i == m + k - )
puts("");
else
printf(" ");
}
return ;
}
puts("LOSE");
return ;
}
上一篇:Openerp 中打开 URL 的三种 方法


下一篇:ORA-00600: [keltnfy-ldmInit], [46], [1], [], [], [], [], []