結果

問題 No.807 umg tours
ユーザー 37zigen37zigen
提出日時 2019-03-22 23:42:49
言語 C++11
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,553 bytes
コンパイル時間 1,810 ms
コンパイル使用メモリ 167,272 KB
実行使用メモリ 30,804 KB
最終ジャッジ日時 2024-11-23 19:12:32
合計ジャッジ時間 12,387 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
11,136 KB
testcase_01 AC 3 ms
5,888 KB
testcase_02 AC 3 ms
5,888 KB
testcase_03 AC 3 ms
5,760 KB
testcase_04 AC 3 ms
5,760 KB
testcase_05 AC 3 ms
5,760 KB
testcase_06 AC 4 ms
6,016 KB
testcase_07 AC 3 ms
5,888 KB
testcase_08 AC 2 ms
5,760 KB
testcase_09 AC 3 ms
6,016 KB
testcase_10 AC 3 ms
5,888 KB
testcase_11 AC 249 ms
12,912 KB
testcase_12 AC 236 ms
12,020 KB
testcase_13 AC 336 ms
13,864 KB
testcase_14 AC 137 ms
9,480 KB
testcase_15 AC 109 ms
8,448 KB
testcase_16 AC 350 ms
14,344 KB
testcase_17 AC 453 ms
17,244 KB
testcase_18 AC 446 ms
17,496 KB
testcase_19 AC 435 ms
15,332 KB
testcase_20 AC 268 ms
11,136 KB
testcase_21 AC 271 ms
11,392 KB
testcase_22 AC 113 ms
8,112 KB
testcase_23 AC 89 ms
7,680 KB
testcase_24 TLE -
testcase_25 AC 452 ms
30,804 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