선거 공약 (PROMISES)

algospot.com :: PROMISES

플로이드-와샬

 

문제 설명

 

우선 기존에 있던 고속도로들을 가지고 플로이드 알고리즘을 통해서 최단거리를 구해준다.

그리고 새로운 고속도로(a에서 b로 가는)가 건설 될 때마다 현재 최단거리와 비교해서 비용이 같거나 오히려 더 크다면 해당 고속도로를 설치할 필요가 없다.

하지만 새로운 고속도로를 설치하는게 이득이 된다면 a에서 b로 가는 고속도로를 추가하고 플로이드 알고리즘을 통해서 모든 간선의 최소비용을 갱신해 준다.

 

r에서 c로 가는 비용을 갱신하기 위해서 a-b 고속도로를 거쳐간다고 생각해보자. 

r-a-b-c 순으로 이동할 수도 있고, r-b-a-c순으로 이동할 수도 있다.

 

1-4 간선은 점선입니다.

만약 위와 같은 그래프가 있다고 생각해보자

 

 1-4를 이루는 간선은 점선(앞으로 건설될 고속도로)이라고 생각하자

 

현재 2-3으로 가기 위해서는 4번을 거쳐서 가는 비용이 11인 도로가 최소이다.

만약 1 4 1 고속도로가 입력으로 주어진다면?

 

2-3으로 가기위해서 2-4-1-3 경로를 따라서 가면 최소비용 10 이 발생한다.

 

따라서 간선의 방향을 고려해서 dp[r][c] = min(dp[r][a] + w[a][b] + dp[b][c], dp[r][b] + w[b][a] + dp[a][c], dp[r][c])

를 점화식으로 가질 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int V, M, N;
int highway[201][201];
 
void init(){
    cin >> V >> M >> N;
    
    for(int i = 0; i < V; i++){
        for(int j = 0; j < V; j++){
            if(i == j) highway[i][j] = 0;
            else highway[i][j] = INF;
        }
    }
    
    int a, b, c;
    for(int i = 0; i < M; i++){
        cin >> a >> b >> c;
        highway[a][b] = min(highway[a][b], c);
        highway[b][a] = min(highway[b][a], c);
    }
    
    for(int i = 0; i < V; i++){
        for(int r = 0; r < V; r++){
            for(int c = 0; c < V; c++){
                highway[r][c] = min(highway[r][c], highway[r][i] + highway[i][c]);
            }
        }
    }
}
 
bool is_valid(int a, int b, int c){
    if(highway[a][b] <= c) return false;
    
    for(int r = 0; r < V; r++){
        for(int c = 0; c < V; c++){
            highway[r][c] = min(highway[r][c], \
                            min(highway[r][a] + c + highway[b][c], \
                                highway[r][b] + c + highway[a][c]));
        }
    }
    
    return true;
}
 
void solve(){
    int ans = 0;
    
    int a, b, c;
    for(int i = 0; i < N; i++){
        cin >> a >> b >> c;
        if(!is_valid(a, b, c)) ans++;
    }
    
    cout << ans << "\n";
}
 
int main(){
    fasti
    int test;
    cin >> test;
    
    while(test--){
        init();
        solve();
    }
    
    return 0;
}