QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #39943 | #4357. School Road | ZeinDaner | 0 | 2ms | 44636kb | C++ | 1.1kb | 2022-07-15 04:38:47 | 2022-07-15 04:38:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<int,ll> il;
typedef vector<il> vil;
const ll MAX=1e18;
vector<vil> G;
int n,m;
ll dp[20][262145];
ll back(int u,int mask){
if(dp[u][mask]!=-1) return dp[u][mask];
if(mask&(1<<(n-1))){
return 0;
}
ll ans=0;
for(auto &v:G[u]){
if(!(mask&(1<<v.first))){
ans=max(ans,back(v.first,mask|(1<<v.first))+v.second);
}
}
return dp[u][mask]=ans;
}
ll dis[20];
void bfs(){
priority_queue<ii, vector<ii>, greater<ii> > pq;
pq.push(ii(0,0));
dis[0]=0;
while(!pq.empty()){
int x=pq.top().second;
for(auto &v:G[x]){
if(dis[v.first]>dis[x]+v.second){
dis[v.first]=dis[x]+v.second;
pq.push(ii(dis[v.first],v.first));
}
}
}
}
int main(){
memset(dp,-1,sizeof dp);
cin>>n>>m;
G.resize(n+1);
for(int i=0;i<m;i++){
int a,b,w; cin>>a>>b>>w;
a--; b--;
G[a].push_back(il(b,w));
G[b].push_back(il(a,w));
}
ll ma=back(0,1);
cout<<(dis[n-1]<ma)<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 44484kb
input:
14 40 8 12 570429827 6 10 592780730 13 14 299807355 4 10 729771483 4 10 729771483 6 9 746405411 2 3 696576351 12 14 192640790 4 13 284900209 1 2 857968292 12 14 192640790 8 12 570429827 6 10 592780730 6 9 746405411 9 11 329648726 4 13 284900209 2 3 696576351 4 10 729771483 5 11 101819611 3 7 1824073...
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 2ms
memory: 44636kb
input:
18 40 3 10 26965732 5 15 67047331 3 17 42474964 13 15 129212204 9 18 142540287 2 14 27157962 5 15 67047331 5 15 67047331 5 15 67047331 4 16 212978971 6 12 51548223 4 18 192438222 13 16 60052417 16 17 162364835 6 17 55527270 9 11 58810843 3 7 95393586 13 15 129212204 2 17 67824762 5 15 67047331 15 16...
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'
Subtask #3:
score: 0
Runtime Error
Test #18:
score: 0
Runtime Error
input:
100000 99999 42115 93495 19881095 21969 68351 161710 7405 86343 27129 37307 45676 320013 30388 71545 117761 22026 68957 65332 77949 81644 2281387 24865 95079 341488 9849 98496 2548159 53911 79572 4962105 24880 62622 1678564 15943 22168 1524688 67424 78323 2450655 32175 74893 1908332 35640 39305 1043...
output:
result:
Subtask #4:
score: 0
Wrong Answer
Test #57:
score: 0
Wrong Answer
time: 2ms
memory: 44512kb
input:
18 400 11 18 145314505 1 18 242896789 1 18 242896789 5 13 31030812 13 18 93451080 1 18 242896789 1 7 123378068 1 18 242896789 1 18 242896789 1 18 242896789 1 18 242896789 1 18 242896789 1 18 242896789 1 3 42183985 1 18 242896789 13 18 93451080 1 18 242896789 13 18 93451080 1 18 242896789 1 18 242896...
output:
1
result:
wrong answer 1st lines differ - expected: '0', found: '1'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%