2135-Reverse a Road

問題概要

有向グラフが与えられる。
その中の一辺を逆向きに出来るとしたときのST間最短路の長さと逆向きにする辺を答えろ

解法

ダイクストラ法
辺を入れかえたか否かと現在の頂点番号を記録する

実装(C++)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define REP(i,x)for(int i=0;i<(int)x;i++)
struct Edge{
	int dst,cost;
};
typedef pair<int,int> P;
typedef vector<Edge> Node;
typedef vector<Node> Graph;
int N,M,S,T;
Graph G;
P d[2000][2];
bool used[2000][2];
void dijkstra(int s){
	memset(d,0x3f,sizeof(d));
	memset(used,0,sizeof(used));
	d[s][0]=P(0,0);
	while(1){
		P mincost=P(99999999,99999999);int mi=-1,mj=0;
		for(int i=0;i<N;i++){
			for(int j=0;j<2;j++){
				if(used[i][j]==false&&mincost>d[i][j]){
					mincost=d[i][j];
					mi=i;mj=j;
				}
			}
		}
		if(mi==-1)break;
		used[mi][mj]=true;
		REP(i,G[mi].size()){
			Edge &e=G[mi][i];
			if(e.cost>0&&mj==0&&mincost.second==0){
				d[e.dst][1]=min(d[e.dst][1],P(mincost.first+1,e.cost));
			}
			if(e.cost==0){
				d[e.dst][mj]=min(d[e.dst][mj],P(mincost.first+1,mincost.second));
			}
		}
	}
}
int main() {
	while(~scanf("%d",&N)){
		if(N==0)break;
		scanf("%d%d%d",&S,&T,&M);S--;T--;
		G=Graph(N);
		for(int i=0;i<M;i++){
			int a,b;
			scanf("%d%d",&a,&b);a--;b--;
			G[a].push_back((Edge){b,0});
			G[b].push_back((Edge){a,i+1});
		}
		dijkstra(S);
		if(d[T][0].first>d[T][1].first){
			cout<<d[T][1].first<<" "<<d[T][1].second<<endl;
		}else{
			cout<<d[T][0].first<<" "<<0<<endl;
		}
	}
}