Submission #58654

ソースコード

#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define _GLIBCXX_DEBUG
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
const int INF = 1 << 30;
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
priority_queue<pint, vector<pint>, greater<pint> > pq;
vector<vector<pint> > lis;
vector<int> mincost;
void dijkstra(int s){
  mincost[s]=0;
  pq.emplace(0,s);
  while(!pq.empty()){
    int nownode,nowcost;
    tie(nowcost,nownode)=pq.top(); pq.pop();
    if(mincost[nownode] < nowcost){
      continue;
    }
    for(int i=0;i<lis[nownode].size();i++){
      int nextnode,nextcost;
      tie(nextnode,nextcost)=lis[nownode][i];
      if(mincost[nownode]+nextcost<mincost[nextnode]){
                mincost[nextnode]=mincost[nownode]+nextcost;
                pq.emplace(mincost[nextnode],nextnode);
      }
    }
  }
}
       
 
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    mincost.resize(n+1,INF);
    lis.resize(n+1);
    int a,b,c;
    for(int i=0;i<m;i++){
      cin>>a>>b>>c;
      lis[a].emplace_back(b,c);
      lis[b].emplace_back(a,c);
    }
    dijkstra(1);
/* rep(i,n){
              cout<<mincost[i]<<' ' ;
    } */
    if(mincost[n]==INF){
      cout<<"NA\n";
    }
    else{
      cout<<mincost[n]<<'\n';
    }
    return(0);
}

ステータス

項目	データ
問題	0431 - 君も始めようダイクストラ大好き厨
ユーザー名	ei1918
投稿日時	2020-02-13 18:13:57
言語	C++14
状態	Accepted
得点	1
ソースコード長	1749 Byte
最大実行時間	99 ms
最大メモリ使用量	10828 KB

セット

	セット	得点	Cases
1	ALL	1 / 1	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
m_in1.txt	AC	99 ms	8664 KB	1
r_in1.txt	AC	65 ms	3476 KB	1
r_in2.txt	AC	35 ms	6120 KB	1
r_in3.txt	AC	30 ms	8324 KB	1
r_in4.txt	AC	31 ms	8852 KB	1
r_in5.txt	AC	38 ms	9472 KB	1
r_in6.txt	AC	32 ms	9920 KB	1
r_in7.txt	AC	36 ms	9184 KB	1
r_in8.txt	AC	29 ms	9400 KB	1
r_in9.txt	AC	67 ms	10828 KB	1
r_in10.txt	AC	30 ms	3168 KB	1
r_in11.txt	AC	32 ms	3908 KB	1
r_in12.txt	AC	39 ms	4112 KB	1
r_in13.txt	AC	43 ms	4644 KB	1
r_in14.txt	AC	36 ms	5084 KB	1
r_in15.txt	AC	30 ms	5336 KB	1
r_in16.txt	AC	45 ms	5528 KB	1
r_in17.txt	AC	41 ms	5892 KB	1
r_in18.txt	AC	30 ms	6180 KB	1
r_in19.txt	AC	28 ms	4996 KB	1
r_in20.txt	AC	33 ms	5868 KB	1
r_in21.txt	AC	83 ms	5644 KB	1
r_in22.txt	AC	19 ms	5860 KB	1
r_in23.txt	AC	24 ms	5968 KB	1
r_in24.txt	AC	36 ms	6236 KB	1
r_in25.txt	AC	36 ms	6696 KB	1
r_in26.txt	AC	30 ms	6900 KB	1
r_in27.txt	AC	68 ms	7228 KB	1
r_in28.txt	AC	30 ms	7496 KB	1
r_in29.txt	AC	39 ms	7824 KB	1
r_in30.txt	AC	32 ms	8536 KB	1