QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153771 | #7048. Delivery Route | PetroTarnavskyi# | WA | 4ms | 15076kb | C++17 | 2.5kb | 2023-08-30 22:28:39 | 2023-08-30 22:28:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 1 << 17;
vector<PII> g[2][N];
int has_path[N];
void dfs1(int v)
{
has_path[v] = 1;
FOR(t, 0, 2)
{
for(auto e : g[t][v])
{
int to = e.F;
if(!has_path[to])
{
dfs1(to);
}
}
}
}
int component[N];
int used[N];
VI verts[N];
int cntin[N];
void dfs2(int v, int comp)
{
used[v] = 1;
component[v] = comp;
verts[comp].PB(v);
for(auto e : g[0][v])
{
int to = e.F;
if(!used[to])
{
dfs2(to, comp);
}
}
}
const int INF = 1e9;
int d[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, x, y, s;
cin >> n >> x >> y >> s;
s--;
FOR(t, 0, 2)
{
FOR(i, 0, x)
{
int a, b, w;
cin >> a >> b >> w;
a--; b--;
g[t][a].PB(MP(b, w));
if(t == 0)
{
g[t][b].PB(MP(a, w));
}
}
swap(x, y);
}
dfs1(s);
int cnt_comp = 0;
FOR(i, 0, n)
{
if(has_path[i] && !used[i])
{
dfs2(i, cnt_comp++);
}
}
FOR(v, 0, n)
{
if(has_path[v])
{
for(auto e : g[1][v])
{
int to = e.F;
assert(component[v] != component[to]);
cntin[component[to]]++;
}
}
}
set<PII> q;
FOR(i, 0, cnt_comp)
{
if(cntin[i] == 0)
{
for(int v : verts[i])
{
d[v] = INF;
q.insert(MP(INF, v));
}
}
}
q.erase(MP(INF, s));
d[s] = 0;
q.insert(MP(0, s));
while(SZ(q))
{
int v = q.begin()->S;
q.erase(q.begin());
FOR(t, 0, 2)
{
for(auto e : g[t][v])
{
int to = e.F;
int w = e.S;
int comp = component[to];
if(t)
{
cntin[comp]--;
assert(cntin[comp] >= 0);
if(cntin[comp] == 0)
{
for(int u : verts[comp])
{
q.insert(MP(d[u], u));
}
}
}
if(d[to] < d[v] + w)
{
continue;
}
if(cntin[comp] == 0)
{
q.erase(MP(d[to], to));
d[to] = d[v] + w;
q.insert(MP(d[to], to));
}
d[to] = d[v] + w;
}
}
}
FOR(i, 0, n)
{
if(!has_path[i])
{
cout << "NO PATH\n";
}
else
cout << d[i] << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 15076kb
input:
6 3 3 4 1 2 5 3 4 5 5 6 10 3 5 -100 4 6 -100 1 3 -10
output:
NO PATH NO PATH 5 0 -95 -100
result:
ok 6 lines
Test #2:
score: -100
Wrong Answer
time: 4ms
memory: 14264kb
input:
100 500 500 4 13 20 329 41 10 63 100 90 297 15 79 163 24 67 747 29 68 443 73 98 565 10 41 921 79 62 973 31 85 270 25 29 672 34 43 391 30 92 604 58 82 90 28 16 460 53 63 350 91 98 260 70 22 232 5 36 335 37 32 339 4 48 940 85 1 233 95 78 323 62 79 688 49 57 576 10 54 103 33 78 541 88 22 171 4 48 408 2...
output:
-3804 -3721 NO PATH 0 NO PATH -7390 -6773 -2428 -3083 -876 -6940 -895 -4421 -4114 -1126 -5012 -4981 NO PATH -7012 -4431 -4944 -2176 -5210 -1707 -6828 -6638 -3269 -4925 -6633 -5737 -3985 -2885 -7191 -4100 -907 NO PATH -2952 NO PATH 158 -2709 -813 -7351 -4044 -3023 -2353 -7291 -2911 112 -4029 0 -4045 ...
result:
wrong answer 1st lines differ - expected: '-3619', found: '-3804'