4210:Almost Shortest Path

問題文
https://icpcarchive.ecs.baylor.edu/external/42/4210.pdf

グラフが与えられる。最短経路に含まれる辺をひとつも使わない経路の中で最短のものを求めよ。ただし最短経路は複数ある場合もある。

ダイクストラを2回やる。一回目で最短経路に含まれる辺をすべて列挙しておく。二回目でその辺を使わないような経路で最短のものを求める。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include<set>
#include <vector>
using namespace std;
 
#define MAX_V 510
#define INF (1<<29)
 
vector<int> prev[MAX_V];
int g[MAX_V][MAX_V],d[MAX_V],n;
bool used[MAX_V];
bool shortest_path[MAX_V][MAX_V];
 
void dijkstra(int s){
  fill(d,d+n,INF);
  fill(used,used+n,false);
  for(int i=0;i<n;i++)prev[i].clear();
  d[s]=0;
   
  while(true){
    int v=-1;
    for(int u=0;u<n;u++){
      if(!used[u] && (v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
 
    for(int u=0;u<n;u++){
      if(shortest_path[v][u])continue;
      if(d[u]>d[v]+g[v][u]){
	d[u]=d[v]+g[v][u];
	prev[u].clear();
	prev[u].push_back(v);
      }
      else if(d[u]==d[v]+g[v][u])prev[u].push_back(v);
    }
  }
}
 
set<int>S;
 
void get_path(int t){
  if(S.count(t))return;
  S.insert(t);
  for(int i=0;i<prev[t].size();i++){
    shortest_path[prev[t][i]][t]=true;
    get_path(prev[t][i]);
  }
}
 
int main(void){
 
  int m;
 
  while(cin >> n >> m,n|m){
    int s,t;
    cin >> s >> t;
    int from,to,cost;
    fill(g[0],g[MAX_V],INF);
 
    for(int i=0;i<m;i++){
      cin >> from >> to >> cost;
      g[from][to]=cost;
    }
    fill(shortest_path[0],shortest_path[MAX_V],false);
    S.clear();
    dijkstra(s);
    get_path(t);
 
    dijkstra(s);
    if(d[t]>=INF)cout << -1 << endl;
    else cout << d[t] << endl;
  }
  return 0;
}