#include #include #include #include #include #include #include #include #include #include #include using namespace std; map>> map1; int E[1000]; int E1[1000]; int E2[1000]; void DI(int i){ priority_queue> pq; E[i-1]=0; pq.push({ 0, i }); while(!pq.empty()){ int cur_dist = -pq.top().first; int cur_node = pq.top().second; list>lis=map1[cur_node]; pq.pop(); while(!lis.empty()){ int nxt_node=lis.back().second; int nxt_dist=lis.back().first+cur_dist; if(E[nxt_node-1]>nxt_dist){ E[nxt_node-1]=nxt_dist; pq.push({-nxt_dist,nxt_node}); } lis.pop_back(); } } } void DI1(int i){ priority_queue> pq; E1[i-1]=0; pq.push({ 0, i }); while(!pq.empty()){ int cur_dist = -pq.top().first; int cur_node = pq.top().second; list>lis=map1[cur_node]; pq.pop(); while(!lis.empty()){ int nxt_node=lis.back().second; int nxt_dist=lis.back().first+cur_dist; if(E1[nxt_node-1]>nxt_dist){ E1[nxt_node-1]=nxt_dist; pq.push({-nxt_dist,nxt_node}); } lis.pop_back(); } } } void DI2(int i){ priority_queue> pq; E2[i-1]=0; pq.push({ 0, i }); while(!pq.empty()){ int cur_dist = -pq.top().first; int cur_node = pq.top().second; list>lis=map1[cur_node]; pq.pop(); while(!lis.empty()){ int nxt_node=lis.back().second; int nxt_dist=lis.back().first+cur_dist; if(E2[nxt_node-1]>nxt_dist){ E2[nxt_node-1]=nxt_dist; pq.push({-nxt_dist,nxt_node}); } lis.pop_back(); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int a,b; cin>>a>>b; for(int i=0;i>m>>n>>k; if(map1.find(m) != map1.end()){ pair p; p.first=k; p.second=n; map1[m].push_back(p); } else{ pair p; p.first=k; p.second=n; list> lis; lis.push_back(p); map1[m]=lis; } if(map1.find(n) != map1.end()){ pair p; p.first=k; p.second=m; map1[n].push_back(p); } else{ pair p; p.first=k; p.second=m; list> lis; lis.push_back(p); map1[n]=lis; } } int m,n; cin>>m>>n; E[0]=0; E1[m-1]=0; E2[n-1]=0; DI(1); DI1(m); DI2(n); if((E[m-1]==INT_MAX&&E[n-1]==INT_MAX)||(E1[n-1]==INT_MAX&&E2[m-1]==INT_MAX)||(E1[a-1]==INT_MAX&&E2[a-1]==INT_MAX)){ cout<<-1; } else{ int min; min=E[m-1]+E1[n-1]+E2[a-1]

제출 #94476

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: