AOJ 0244 - Hot Spring Trip

時間はかかったけど自分で解けた．嬉しい．
dijkstra法っぽい気がしたけど，違う気もする．

#include<iostream>
#include<vector>

struct Edge{
	int to, cost;
};

const int INF = 1 << 24;
int n, m;
int d[2][100];
std::vector<Edge> es[100];

void dijkstra(int s){
	int used[2][100];
	for(int i=0;i<2;i++){
		for(int j=0;j<n;j++){
			used[i][j] = 0;
			d[i][j] = INF;
		}
	}

	d[0][s] = 0;

	while(true){
		int u = -1, v;
		for(int i=0;i<2;i++){
			for(int j=0;j<n;j++){
				if(!used[i][j] && (u == -1 || d[i][j] < d[u][v])){
					u = i;
					v = j;
				}
			}
		}

		if(u == -1)break;
		used[u][v] = 1;

		for(int i=0;i<es[v].size();i++){
			Edge e1 = es[v][i];
			d[u][e1.to] = std::min(d[u][e1.to], d[u][v]+e1.cost);
			for(int j=0;j<es[e1.to].size();j++){
				Edge e2 = es[e1.to][j];
				if(v != e2.to && u == 0){
					d[1][e2.to] = std::min(d[1][e2.to], d[0][v]);
				}
			}
		}
	}
}

int main(){
	while(std::cin >> n >> m, n){
		for(int i=0;i<n;i++){
			es[i].clear();
		}
		for(int i=0;i<m;i++){
			int a, b, c;
			std::cin >> a >> b >> c;
			es[a-1].push_back({b-1, c});
			es[b-1].push_back({a-1, c});
		}

		dijkstra(0);

		std::cout << std::min(d[0][n-1], d[1][n-1]) << std::endl;
	}
}