[백준] 2311 왕복 여행

문제

N개의 나라가 있고, 이들 중 몇 개의 나라들은 서로 도로로 연결되어 있다. 편의상 N개의 나라들은 각각 1, 2, ..., N의 번호가 붙어 있다고 하자. i번 나라와 j번 나라가 도로로 연결되어 있으면 i번 나라에서 j번 나라로 이동할 수 있고, j번 나라에서 i번 나라로도 이동할 수 있다. 당신은 1번 나라에 살고 있다.

여름을 맞이하여 당신은 N번 나라로 왕복 여행을 다녀오려고 한다. 즉 1번 나라에서 N번 나라로 갔다가 다시 1번 나라로 돌아오고자 한다. 아쉽게도 각 도로의 이용권이 한 장씩밖에 주어져 있지 않아서, 한 번 지난 도로는 다시 지날 수 없다고 한다. 이때, 여행에 소요되는 최소 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000) 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 자연수 A, B, C가 주어진다. 이는 A번 나라와 B번 나라가 도로로 연결되어 있으며, 이 도로를 지날 때 걸리는 시간이 C임을 의미한다. (1 ≤ A ≤ N, 1 ≤ B ≤ N, 1 ≤ C ≤ 50,000) 두 나라 사이에 두 개 이상의 도로가 있는 경우는 없다고 가정한다. 항상 왕복할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 여행에 소요되는 최소 시간을 출력한다.

 

MCMF문제입니다.

한 정점은 여러번 방문 가능하지만, 한 간선은 한번만 이용가능합니다.

따라서, 정점을 분할하여 모델링합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

using namespace std;
int N, M, x, y, z, c[2003][2003], f[2003][2003], cost[2003][2003], ans;
vi adj[2003];
//in : v
//out: v + N

int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		cin >> x >> y >> z;
		c[x + N][y] = 1;
		c[y + N][x] = 1;

		adj[x + N].push_back(y);
		adj[y].push_back(x + N);

		adj[y + N].push_back(x);
		adj[x].push_back(y + N);

		cost[x + N][y] = z;
		cost[y][x + N] = -z;

		cost[y + N][x] = z;
		cost[x][y + N] = -z;
	}
	REP(i, N) {
		adj[i].push_back(i + N);
		adj[i + N].push_back(i);
		c[i][i + N] = INF;
	}
	rep(i,2) {
		queue<int>q;
		int dist[2003], p[2003], inQ[2003];
		fill(p, p + 2003, -1);
		fill(dist, dist + 2003, INF);
		mset(inQ);
		q.push(1 + N);
		p[1 + N] = 1;
		inQ[1+N] = 1;
		dist[1+N] = 0;
		while (!q.empty()) {
			int cur = q.front();
			inQ[cur] = 0;
			q.pop();
			for (int nxt : adj[cur]) {
				if (c[cur][nxt] - f[cur][nxt] > 0 && dist[nxt] > dist[cur] + cost[cur][nxt]) {
					p[nxt] = cur;
					dist[nxt] = dist[cur] + cost[cur][nxt];
					if (!inQ[nxt]) {
						q.push(nxt);
						inQ[nxt] = 1;
						if (nxt == N)break;
					}
				}
			}
		}
		for (int i = N; i != 1+N; i = p[i]) {
			ans += cost[p[i]][i];
			f[p[i]][i] += 1;
			f[i][p[i]] -= 1;
		}
	}
	cout << ans;
}