AOJ 0212 Highway Express Bus

これは良問だと思った。
これを機にダイクストラ法の理解が一層深まった気がする。
解説
まず、下のコードではdpテーブルはdとおいて、d[0][i]に普通のダイクストラ法をやっていく。その後にmin(~,~)で割引券を使った時と使ってない時を判定して、最短経路を求めていく。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;
typedef pair<int, int> P;

const int INF = 1 << 30;

struct edge {int to, cost; };

int V;
int d[100][100];

vector<edge> G[100];
priority_queue<P, vector<P>, greater<P> > que;

void dijkstra(int s,int a){
  for(int i = 0; i < V; i++) d[a][i] = INF;
  que.push(P(0, s));
  d[a][s] = 0;

  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.second;
    if(d[a][v] < p.first) continue;
    for(int i = 0; i < G[v].size(); i++){
      edge e = G[v][i];
      int Min = (a == 0 ? d[a][v] + e.cost : min(d[a][v] + e.cost, d[a-1][v] + e.cost/2));
      if(d[a][e.to] > Min){
        d[a][e.to] = Min;
        que.push(P(d[a][e.to], e.to));
      }
    }
  }
}

int main(){
  int c,m,s,e,From,To,Cost;
  edge E;
  while(scanf("%d%d%d%d%d",&c,&V,&m,&s,&e)!=EOF,c|V|m|s--|e--){
    for(int i = 0; i < m; i++){
      scanf("%d%d%d",&From,&To,&Cost);
          
      From--,To--;
      E.to = From,E.cost = Cost;
      G[To].push_back(E);
      E.to = To;
      G[From].push_back(E);
    }
    
    for(int i = 0; i <= c; i++) dijkstra(s, i);
    
    printf("%d\n",d[c][e]);
    
    for(int i = 0; i < 100; i++) G[i].clear();
  }
}