結果

問題 No.807 umg tours
ユーザー 37zigen
提出日時 2019-03-22 23:42:49
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 785 ms
コード長 1,553 Byte
コンパイル時間 1,210 ms
使用メモリ 15,500 KB
最終ジャッジ日時 2019-08-18 03:05:41

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0small1.txt AC 6 ms
3,880 KB
0small2.txt AC 6 ms
3,880 KB
0small3.txt AC 7 ms
3,892 KB
0small4.txt AC 6 ms
3,888 KB
0small5.txt AC 8 ms
3,868 KB
0small6.txt AC 7 ms
3,880 KB
0small7.txt AC 7 ms
3,892 KB
0small8.txt AC 7 ms
3,888 KB
1perfect1.txt AC 7 ms
3,864 KB
1perfect2.txt AC 6 ms
3,868 KB
1perfect3.txt AC 7 ms
3,872 KB
2large1.txt AC 413 ms
10,864 KB
2large2.txt AC 430 ms
10,200 KB
2large3.txt AC 591 ms
11,816 KB
2large4.txt AC 229 ms
7,412 KB
2large5.txt AC 175 ms
6,576 KB
2large7.txt AC 585 ms
12,292 KB
3largest1.txt AC 785 ms
15,364 KB
3largest2.txt AC 734 ms
15,500 KB
3largest3.txt AC 711 ms
13,368 KB
4tree1.txt AC 395 ms
9,268 KB
4tree2.txt AC 402 ms
9,464 KB
4tree3.txt AC 158 ms
6,292 KB
4tree4.txt AC 121 ms
5,776 KB
99_system_test1.txt AC 736 ms
15,268 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>

std::vector< std::pair<int,int> > g[100000];
long long dp[2][100000];

struct state{
  int id;
  bool used;
  long long dist;
  
};

bool operator> (const state &state1, const state &state2){
  if(state1.dist==state2.dist){
    return !state1.used;
  }else{
    return state1.dist>state2.dist;
  }
}

int main(){
  
  int N, M;
  std::cin>>N>>M;
  
   for(int i=0;i<M;++i)
     {
       int a,b,c;
       std::cin>>a>>b>>c;
       --a;
       --b;
       g[a].push_back(std::make_pair(b,c));
       g[b].push_back(std::make_pair(a,c));
     }
   
   for(int i=0;i<2;++i)
     {
     for(int j=0;j<N;++j)
       {
	 dp[i][j]=1LL<<60;
       }
     }
   
   dp[0][0]=0;
   
   std::priority_queue<state, std::vector<state>, std::greater<state> > pq;
   
   state src={0,false,0};//id,used,dist
   pq.push(src);
   while(!pq.empty()){
     state s = pq.top();
     pq.pop();
     for(std::pair<int, int> dst:g[s.id])
       {
	 if(!s.used&&dp[1][dst.first]>dp[0][s.id])
	   {
	     dp[1][dst.first]=dp[0][s.id];
	     state add= {dst.first,true,dp[1][dst.first]};
	     pq.push(add);
	   }
	 
	 {
	   int p = s.used?1:0;
	   if(dp[p][dst.first]>dp[p][s.id]+dst.second)
	     {
	       dp[p][dst.first]=dp[p][s.id]+dst.second;
	       state add = {dst.first, s.used, dp[p][dst.first]};
	       pq.push(add);
	     }
	 }
	 
       }
   }

   for(int i=0;i<N;++i)
     {
       dp[1][i]=std::min(dp[1][i],dp[0][i]);
     }
   for(int i=0;i<N;++i)
     {
       std::cout<<dp[0][i]+dp[1][i]<<std::endl;
     }
   
   
   return 0;
}

0