Submission #1088429
Source Code Expand
#include<bits/stdc++.h> #define P pair<int,int> using namespace std; vector<P>rinsetu[1000]; int mincost[1000]; int n[1000]; signed main(){ int a,b,c,d;cin>>a>>b>>c>>d;c--;d--; if(c==d){puts("-1");return 0;} for(int e=0;e<b;e++){ int f,g,h;scanf("%d%d%d",&f,&g,&h);f--;g--; rinsetu[f].push_back(P(h,g)); rinsetu[g].push_back(P(h,f)); } fill(mincost+1,mincost+a,1<<29); fill(n,n+a,1<<29); n[d]=0; priority_queue<P,vector<P>,greater<P>>Q; Q.push(P(0,c)); while(Q.size()){ P t=Q.top();Q.pop(); if(t.first>mincost[t.second])continue; for(P i:rinsetu[t.second]){ if(mincost[i.second]>t.first+i.first){ mincost[i.second]=t.first+i.first; Q.push(P(mincost[i.second],i.second)); } } } while(Q.size())Q.pop(); Q.push(P(0,d)); while(Q.size()){ P t=Q.top();Q.pop(); if(t.first>n[t.second])continue; for(P i:rinsetu[t.second]){ if(n[i.second]>t.first+i.first){ n[i.second]=t.first+i.first; Q.push(P(n[i.second],i.second)); } } } for(int i=0;i<a;i++){ if(mincost[i]==n[i]){cout<<i+1<<endl;return 0;} } puts("-1"); }
Submission Info
Submission Time | |
---|---|
Task | C - 身体バランス |
User | naoki2016 |
Language | C++11 (GCC 4.8.1) |
Score | 0 |
Code Size | 1190 Byte |
Status | WA |
Exec Time | 29 ms |
Memory | 1308 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:12:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int f,g,h;scanf("%d%d%d",&f,&g,&h);f--;g--; ^
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00-sample-00, 00-sample-01, corner-case-01, corner-case-02, corner-case-03, largest-00, largest-01, largest-02, largest-03, largest-04, largest-05, random-00-0934, random-01-0457, random-02-0288, random-03-0873, random-04-0364, random-05-0053, random-06-0613, random-07-0729, random-08-0061, random-09-0645, random-10-0095, random-11-0369, random-12-0115, random-13-0260, random-14-0033, random-15-0579, random-16-0713, random-17-0336, random-18-0297, random-19-0826, random-20-0742, random-21-0264, random-22-0507, random-23-0502, random-24-0750, random-25-0721, random-26-0043, random-27-0348, random-28-0756, random-29-0647, random-30-0854, random-31-0554, random-32-0632, random-33-0776, random-34-0165, random-35-0695, random-36-0136, random-37-0831, random-38-0284, random-39-0610, random-40-0421 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample-00 | AC | 17 ms | 924 KB |
00-sample-01 | AC | 20 ms | 920 KB |
corner-case-01 | WA | 19 ms | 916 KB |
corner-case-02 | WA | 19 ms | 916 KB |
corner-case-03 | WA | 18 ms | 924 KB |
largest-00 | AC | 22 ms | 1180 KB |
largest-01 | AC | 22 ms | 1304 KB |
largest-02 | AC | 22 ms | 1176 KB |
largest-03 | AC | 22 ms | 1180 KB |
largest-04 | AC | 22 ms | 1212 KB |
largest-05 | AC | 20 ms | 1176 KB |
random-00-0934 | AC | 22 ms | 1180 KB |
random-01-0457 | AC | 22 ms | 1180 KB |
random-02-0288 | AC | 22 ms | 1172 KB |
random-03-0873 | AC | 22 ms | 1168 KB |
random-04-0364 | AC | 22 ms | 1180 KB |
random-05-0053 | AC | 19 ms | 924 KB |
random-06-0613 | AC | 29 ms | 1212 KB |
random-07-0729 | AC | 22 ms | 1304 KB |
random-08-0061 | AC | 19 ms | 1048 KB |
random-09-0645 | AC | 21 ms | 1304 KB |
random-10-0095 | AC | 17 ms | 924 KB |
random-11-0369 | AC | 18 ms | 1048 KB |
random-12-0115 | AC | 18 ms | 924 KB |
random-13-0260 | AC | 20 ms | 1052 KB |
random-14-0033 | AC | 19 ms | 924 KB |
random-15-0579 | WA | 18 ms | 1052 KB |
random-16-0713 | AC | 20 ms | 1180 KB |
random-17-0336 | AC | 21 ms | 1308 KB |
random-18-0297 | AC | 20 ms | 1308 KB |
random-19-0826 | AC | 22 ms | 1172 KB |
random-20-0742 | AC | 21 ms | 1176 KB |
random-21-0264 | AC | 22 ms | 1180 KB |
random-22-0507 | AC | 21 ms | 1176 KB |
random-23-0502 | AC | 20 ms | 1180 KB |
random-24-0750 | AC | 22 ms | 1180 KB |
random-25-0721 | AC | 20 ms | 1172 KB |
random-26-0043 | AC | 19 ms | 1048 KB |
random-27-0348 | AC | 20 ms | 1180 KB |
random-28-0756 | AC | 22 ms | 1304 KB |
random-29-0647 | AC | 22 ms | 1304 KB |
random-30-0854 | AC | 22 ms | 1180 KB |
random-31-0554 | WA | 22 ms | 1180 KB |
random-32-0632 | AC | 20 ms | 1048 KB |
random-33-0776 | AC | 23 ms | 1212 KB |
random-34-0165 | AC | 22 ms | 1180 KB |
random-35-0695 | AC | 20 ms | 1052 KB |
random-36-0136 | AC | 20 ms | 1176 KB |
random-37-0831 | AC | 22 ms | 1308 KB |
random-38-0284 | AC | 21 ms | 1304 KB |
random-39-0610 | WA | 22 ms | 1176 KB |
random-40-0421 | AC | 22 ms | 1176 KB |
sample-00 | AC | 19 ms | 924 KB |
sample-01 | AC | 17 ms | 920 KB |