結果

問題 No.807 umg tours
ユーザー 37zigen37zigen
提出日時 2019-03-22 23:42:49
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,553 bytes
コンパイル時間 2,929 ms
コンパイル使用メモリ 153,276 KB
実行使用メモリ 18,228 KB
最終ジャッジ日時 2023-08-15 12:09:01
合計ジャッジ時間 11,246 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,700 KB
testcase_01 AC 3 ms
5,736 KB
testcase_02 AC 4 ms
5,780 KB
testcase_03 AC 3 ms
5,716 KB
testcase_04 AC 3 ms
5,740 KB
testcase_05 AC 3 ms
5,764 KB
testcase_06 AC 4 ms
6,016 KB
testcase_07 AC 3 ms
5,744 KB
testcase_08 AC 3 ms
5,800 KB
testcase_09 AC 3 ms
5,720 KB
testcase_10 AC 2 ms
5,752 KB
testcase_11 AC 224 ms
12,584 KB
testcase_12 AC 234 ms
11,864 KB
testcase_13 AC 310 ms
13,572 KB
testcase_14 AC 138 ms
9,224 KB
testcase_15 AC 112 ms
8,324 KB
testcase_16 AC 329 ms
14,112 KB
testcase_17 AC 426 ms
18,228 KB
testcase_18 AC 423 ms
18,116 KB
testcase_19 AC 406 ms
15,168 KB
testcase_20 AC 241 ms
10,924 KB
testcase_21 AC 246 ms
11,088 KB
testcase_22 AC 105 ms
8,060 KB
testcase_23 AC 82 ms
7,736 KB
testcase_24 TLE -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

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