9 도 1343: 도시 간 도로망 (최 단 경로 변형)

제목 설명:
A 국 정 부 는 도시 간 통행 과 물자 이동 속 도 를 높이 기 위해 국내 N 개 중대 형 도시 사이 에 K 개 도 로 를 추가 로 건설 하기 로 했다.이 N 개 도시 중 어느 두 도시 가 서로 연결 되 고 가장 짧 은 경로 의 길 이 를 알 고 있 습 니 다.새로운 도로 건설 이 A 개국 도시 에 미 친 영향 을 시시각각 감시 하기 위해 서 당신 을 관찰자 로 임명 합 니 다. 도 로 를 건설 할 때마다 해당 국가의 지도자 에 게 현재 N 개 도시 간 의 최 단 로 의 합 을 보고 하 는 것 을 책임 집 니 다.
 
사고의 방향
1. 이 문 제 는 플 로 이 드 알고리즘 의 변형 입 니 다. 문 제 는 이미 임의의 두 도시 간 의 최 단 거 리 를 제 시 했 습 니 다. 매번 에 하나의 도 로 를 추가 하고 이 도 로 를 증가 한 후에 각 도시 간 의 최 단 경로 의 합 이 얼마나 줄 어 들 었 는 지 설명 합 니 다.
 
2. floyd 알고리즘 설명 은 다음 과 같다.
Floyd - Warshall 알고리즘 의 원 리 는 동적 기획 이다
집합 중의 노드 만 중간 노드 로 하 는 가장 짧 은 경로 의 길이 로 설정 합 니 다.

가장 짧 은 경로 가 k 를 지나 면;

가장 짧 은 경로 가 k 를 거치 지 않 으 면.

그래서
실제 알고리즘 에서 공간 을 절약 하기 위해 원래 의 공간 에서 직접 교체 할 수 있다. 그러면 공간 은 2 차원 으로 내 려 갈 수 있다.

for k ← 1 to n do

  for i ← 1 to n do

    for j ← 1 to n do

      if (D_{i,k} + D_{k,j} < D_{i,j}) then

        D_{i,j} ← D_{i,k} + D_{k,j};

 
3. 알고리즘 초기 화 시 dp [i] [i] = 0 을 설정 하면 판단 을 줄 일 수 있 습 니 다.
오류 점: i, j 는 모두 1 부터 시작 합 니 다. j 는 i + 1 부터 시작 하 는 것 이 아 닙 니 다.
 
4. 각 도시 간 의 가장 짧 은 경 로 는?

int sum() {

    int res = 0;

        for(int i = 1; i <= n; i ++)

            for(int j = i+1; j <= n; j ++)

                res += dist[i][j];

    return res;

} 

 
코드

#include <iostream> #include <stdio.h>

using namespace std; const int INF = 0X3F3F3F3F; int dist[400][400]; int n, k; int sum() { int res = 0; for(int i = 1; i <= n; i ++) for(int j = i+1; j <= n; j ++) res += dist[i][j]; return res; } int main() { freopen("testcase.txt", "r", stdin); while(scanf("%d", &n) != EOF) { for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { scanf("%d", &dist[i][j]); } } scanf("%d", &k); int fm, to, d; for(int i = 0; i < k; i ++) { scanf("%d%d%d", &fm, &to, &d); for(int a = 1; a <= n; a ++) { for(int b = 1; b <= n; b ++) {                    // WA

                    if(d+dist[a][fm]+dist[to][b] < dist[a][b]) { dist[a][b] = d+dist[a][fm]+dist[to][b]; dist[b][a] = dist[a][b];                // WA

 } } } int res = sum(); cout << res << endl; } } return 0; }