QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#69947 | #4437. Link with Running | BowieSHI | WA | 690ms | 17744kb | C++14 | 5.3kb | 2023-01-03 16:41:43 | 2023-01-03 16:41:46 |
Judging History
answer
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#define INF 1e18
#define MAXN 300010
using namespace std;
typedef long long ll;
struct edge{
int v,w,c,nxt;
}e[MAXN<<1];
struct Node{
int x;
ll d;
bool operator < (const Node &rhs) const
{
return d>rhs.d;
}
};
int n,m,t,cnt;
int head[MAXN],deg[MAXN];
ll dis[MAXN],C[MAXN];
priority_queue<Node>Q;
bool used[MAXN];
void add (int u,int v,int w,int c)
{
e[cnt].v=v;
e[cnt].w=w;
e[cnt].c=c;
e[cnt].nxt=head[u];
head[u]=cnt++;
}
vector<int>V;
void dfs (int u)
{
used[u]=1;
for (int i=head[u];i!=-1;i=e[i].nxt)
if (e[i].w==0)
{
deg[e[i].v]++;
if (!used[e[i].v]) dfs (e[i].v);
}
}
queue<int>q;
void dij ()
{
dis[1]=0,C[1]=0;
Q.push ((Node){1,dis[1]});
while (1)
{
ll dd=-1;
while (!Q.empty ())
{
int u=Q.top().x;
if (used[u]) Q.pop ();
else
{
dd=dis[u];
break;
}
}
if (dd==-1||Q.empty ()) break;
V.clear ();
while (!Q.empty())
{
int u=Q.top().x;
if (dis[u]!=dd) break;
Q.pop ();
if (used[u]) continue;
V.push_back (u);
used[u]=1;
}
for (int i=0;i<V.size ();i++)
dfs (V[i]);
for (int i=0;i<V.size ();i++)
if (deg[V[i]]==0) q.push (V[i]);
if (t==6)
{
//for (int i=head[1];i!=-1;i=e[i].nxt)
// if (e[i].w==0)
// cout<<e[i].v<<<<" ";
//cout<<endl;
for (int i=1;i<=n;i++) if (used[i]==1) cout<<i<<" ";
exit (0);
}
while (!q.empty ())
{
int u=q.front();
q.pop ();
for (int i=head[u];i!=-1;i=e[i].nxt)
if (e[i].w==0)
{
deg[e[i].v]--;
if (dis[e[i].v]>dis[u]+e[i].w||(dis[e[i].v]==dis[u]+e[i].w&&C[e[i].v]<C[u]+e[i].c))
{
dis[e[i].v]=dis[u]+e[i].w;
C[e[i].v]=C[u]+e[i].c;
}
if (deg[e[i].v]==0) q.push (e[i].v);
}
else
{
if (dis[e[i].v]>dis[u]+e[i].w||(dis[e[i].v]==dis[u]+e[i].w&&C[e[i].v]<C[u]+e[i].c))
{
dis[e[i].v]=dis[u]+e[i].w;
C[e[i].v]=C[u]+e[i].c;
Q.push (((Node){e[i].v,dis[e[i].v]}));
}
}
}
}
}
int main()
{
scanf ("%d",&t);
while (t--)
{
cnt=0;
memset (used,0,sizeof (used));
memset (deg,0,sizeof (deg));
scanf ("%d%d",&n,&m);
for (int i=1;i<=n;i++) head[i]=-1;
for (int i=1;i<=m;i++)
{
int u,v,w,c;
scanf ("%d%d%d%d",&u,&v,&w,&c);
add (u,v,w,c);
}
for (int i=1;i<=n;i++) dis[i]=INF,C[i]=-INF;
dij ();
printf ("%lld %lld\n",dis[n],C[n]);
}
return 0;
}
/*
2
3 3
1 2 1 1
2 3 1 1
1 3 2 0
3 3
1 2 1 1
2 3 1 1
1 3 1 0
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 690ms
memory: 17744kb
input:
12 100000 200000 1 2 838279516 902819511 1 3 293478832 513256010 2 4 682688353 204481674 2 5 360092507 651108247 5 6 519851939 323803002 6 7 675439277 205804465 7 8 419167205 386168059 6 9 140767493 382483305 9 10 558115401 613738466 9 11 902235661 744659643 9 12 851394758 1720015 12 13 635355827 46...
output:
5927443549 11285847934 2529348 325344428756 2522027 438209666288 250100947 25049026205784 249512452 24966236662852 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65...
result:
wrong answer 6th lines differ - expected: '0 9535132634', found: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...99996 99997 99998 99999 100000 '