結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0small1.txt AC 6 ms
3,880 KB
0small2.txt AC 5 ms
3,884 KB
0small3.txt AC 6 ms
3,896 KB
0small4.txt AC 7 ms
3,888 KB
0small5.txt AC 6 ms
3,872 KB
0small6.txt AC 6 ms
3,876 KB
0small7.txt AC 7 ms
3,892 KB
0small8.txt AC 6 ms
3,888 KB
1perfect1.txt AC 5 ms
3,868 KB
1perfect2.txt AC 6 ms
3,868 KB
1perfect3.txt AC 6 ms
3,876 KB
2large1.txt AC 387 ms
10,860 KB
2large2.txt AC 371 ms
10,200 KB
2large3.txt AC 515 ms
11,816 KB
2large4.txt AC 211 ms
7,416 KB
2large5.txt AC 161 ms
6,576 KB
2large7.txt AC 525 ms
12,292 KB
3largest1.txt AC 713 ms
15,364 KB
3largest2.txt AC 697 ms
15,496 KB
3largest3.txt AC 668 ms
13,364 KB
4tree1.txt AC 364 ms
9,268 KB
4tree2.txt AC 387 ms
9,460 KB
4tree3.txt AC 151 ms
6,288 KB
4tree4.txt AC 116 ms
5,776 KB
99_system_test1.txt AC 717 ms
15,264 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