QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18098 | #2178. Robot | _silhouette_# | 0 | 33ms | 22248kb | C++ | 2.4kb | 2022-01-16 11:04:07 | 2022-05-04 17:04:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int Max_N=1e5,Max_M=2e5,B=1e6;
const long long Inf=1e18;
int n,m,Num,lin[Max_N+5];
long long sum[Max_M+5],dis[2][Max_N+5],vis[2][Max_N+5];
struct Edge_fir{ int u,v,c,p; } E[Max_M+5];
vector<int> a[Max_N+5];
priority_queue< pair< long long, long long > > Q;
struct Edge{
int Next,Id,c;
long long val;
} e[Max_M*8+5];
void Insert(int x,int y,int c,long long w){
e[++Num].Next=lin[x]; lin[x]=Num; e[Num].Id=y; e[Num].c=c; e[Num].val=w;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].c,&E[i].p);
a[E[i].u].push_back(i),a[E[i].v].push_back(i);
}
for(int x=1;x<=n;x++){
for(int i=0;i<a[x].size();i++)
sum[E[a[x][i]].c]+=E[a[x][i]].p;
for(int i=0;i<a[x].size();i++)
Insert(x,x^E[a[x][i]].v^E[a[x][i]].u,a[x][i],E[a[x][i]].p),
Insert(x,x^E[a[x][i]].v^E[a[x][i]].u,-a[x][i],sum[E[a[x][i]].c]-E[a[x][i]].p);
for(int i=0;i<a[x].size();i++)
sum[E[a[x][i]].c]-=E[a[x][i]].p;
}
for(int i=0;i<=2;i++)
for(int j=1;j<=max(n,m);j++)
dis[i][j]=Inf;
Q.push(make_pair(0,-1+n)); dis[2][1]=0;
for(;Q.size();){
int c=Q.top().second/B;
int op=Q.top().second%B-n; Q.pop();
if(op<0) {
int x=-op;
if(vis[2][x]) continue; vis[2][x]=1;
for(int i=lin[x];i;i=e[i].Next){
if(e[i].c<0){
int To=x^E[-e[i].c].u^E[-e[i].c].v;
if(dis[2][x]+e[i].val<dis[2][To])
dis[2][To]=dis[2][x]+e[i].val,
Q.push(make_pair(-dis[2][To],-To+n));
} else {
int np=x==E[e[i].c].u?1:0;
if(dis[2][x]+e[i].val<dis[np][e[i].c])
dis[np][e[i].c]=dis[2][x]+e[i].val,
Q.push(make_pair(-dis[np][e[i].c],1ll*e[i].c*B+np+n));
}
}
} else {
if(vis[op][c]) continue; vis[op][c]=1;
int x=op?E[c].v:E[c].u;
for(int i=lin[x];i;i=e[i].Next){
if(e[i].c<0){
int To=x^E[-e[i].c].u^E[-e[i].c].v;
if(dis[op][c]+e[i].val-E[c].p<dis[2][To])
dis[2][To]=dis[op][c]+e[i].val-E[c].p,
Q.push(make_pair(-dis[2][To],-To+n));
} else {
int np=x==E[e[i].c].u?1:0;
if(dis[op][x]+e[i].val<dis[np][e[i].c])
dis[np][e[i].c]=dis[op][x]+e[i].val,
Q.push(make_pair(-dis[np][e[i].c],1ll*e[i].c*B+np+n));
}
}
}
}
long long ans=dis[2][n];
for(int i=1;i<=m;i++)
if(E[i].u==n) ans=min(ans,dis[0][i]);
else if(E[i].v==n) ans=min(ans,dis[1][i]);
printf("%lld\n",ans==Inf?-1:ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 34
Accepted
time: 0ms
memory: 16008kb
input:
2 1 1 2 1 10
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 2ms
memory: 12052kb
input:
8 1 5 6 1 7
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 16080kb
input:
8 19 4 8 15 5 7 8 15 6 1 4 15 6 3 4 2 10 2 7 15 10 5 6 2 10 1 7 2 3 4 5 15 7 1 6 15 6 2 5 2 6 1 8 15 2 1 2 15 9 5 7 2 5 3 8 2 5 4 7 2 6 6 7 15 8 3 7 15 6 2 8 2 1 5 8 15 6
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 5ms
memory: 11984kb
input:
4 6 1 2 1 7 3 4 1 10 2 3 2 5 2 4 1 4 1 4 6 2 1 3 1 2
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 11928kb
input:
64 106 7 46 100 641441921 4 22 92 909042053 27 46 100 185644091 52 54 100 333473988 21 41 69 747879553 23 45 24 121784836 16 23 69 538978180 15 42 92 403583091 49 60 69 112127397 44 48 21 733685727 18 40 92 287239281 3 30 48 498139743 21 25 24 281665265 13 24 69 315527284 12 35 21 100990101 33 56 10...
output:
-1
result:
ok single line: '-1'
Test #6:
score: -34
Wrong Answer
time: 1ms
memory: 14060kb
input:
10 45 6 7 29 19322896 6 8 29 826842878 5 9 29 229755065 1 6 29 49301462 4 10 29 356862039 3 7 29 377906409 8 10 29 877820670 4 8 29 150486169 1 10 29 291057766 1 5 29 982043864 1 3 29 126557279 5 6 29 721959799 3 10 29 636909401 1 7 29 772752473 5 8 29 523364181 7 9 29 250673970 2 6 29 417264209 2 4...
output:
291057766
result:
wrong answer 1st lines differ - expected: '255671682', found: '291057766'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 33ms
memory: 22248kb
input:
25437 78923 921 9998 30945 1 5452 13736 24464 1 11746 24238 24464 1 10875 12958 24464 1 12267 20617 30945 1 3738 16549 35589 1 16223 16940 35589 1 1303 23059 24464 1 12424 21853 24464 1 11198 20674 35589 1 15645 19099 30945 1 8860 9441 24464 1 3609 15160 35589 1 22638 23472 24464 1 766 8991 35589 1 ...
output:
-1
result:
wrong answer 1st lines differ - expected: '5', found: '-1'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%