QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #18101 | #2178. Robot | _silhouette_# | 0 | 93ms | 25800kb | C++ | 2.4kb | 2022-01-16 11:06:45 | 2022-05-04 17:04:51 |
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][c]+e[i].val<dis[np][e[i].c])
dis[np][e[i].c]=dis[op][c]+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: 4ms
memory: 11980kb
input:
2 1 1 2 1 10
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 4ms
memory: 9912kb
input:
8 1 5 6 1 7
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 3ms
memory: 11852kb
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: 11968kb
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: 4ms
memory: 16156kb
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: 0
Accepted
time: 0ms
memory: 11980kb
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:
255671682
result:
ok single line: '255671682'
Test #7:
score: -34
Wrong Answer
time: 4ms
memory: 14160kb
input:
71 788 5 24 146 614916874 56 61 567 467226384 16 44 275 490241032 14 25 567 779488700 19 42 262 524833651 6 19 567 912315689 8 21 774 326632848 46 62 675 296672130 27 32 715 104878301 13 47 675 546642528 18 68 675 349712771 8 43 146 305351688 13 58 567 776051722 49 63 601 454628166 30 43 715 7695855...
output:
124572617
result:
wrong answer 1st lines differ - expected: '46083838', found: '124572617'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 93ms
memory: 25800kb
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:
6
result:
wrong answer 1st lines differ - expected: '5', found: '6'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%