PKU : 3159 - Candies

問題概要

http://poj.org/problem?id=3159
有向グラフが与えられます.
ノード１からＮまでの最短コストを求めてください.

アルゴリズム

ダイクストラで解くだけです.
Time Limitちょうどで通りました.

プログラム

typedef pair<ll,int> P;

vector<P> t[30002];
ll closed[30002];

int main(void){
  int n,m;
  scanf("%d%d",&n,&m);

  while(m--){
    int a,b;
    ll cost;
    scanf("%d%d%lld",&a,&b,&cost);
    a--;
    b--;
    t[a].push_back(P(cost,b));
  }

  priority_queue<P,vector<P>,greater<P> > open;
  rep(i,n) closed[i] = LLONG_MAX;
  open.push(P(0,0));

  while(!open.empty()){
    P p = open.top(); open.pop();
    if(closed[p.second] < p.first) continue;
    if(p.second == n-1){
      printf("%lld\n",p.first);
      break;
    }

    int size = t[p.second].size();
    rep(i,size){
      int nid = t[p.second][i].second;
      ll ncost = p.first + t[p.second][i].first;

      if(closed[nid] > ncost){
        closed[nid] = ncost;
        open.push(P(ncost,nid));
      }
    }
  }
}