Algoogle

Algorithm for Programming Contest

AOJ 2386 Sightseeing Tour

Category: AOJ Tag: graph

Sightseeing Tour

問題概要


解法


すべての点と点の間に2つの有向パスがあるグラフを考える.
完全グラフではパスの向きにかかわらず, 必ずハミルトン路が存在する.
よって2点間のパスのうちコストが小さい方を選んでいけばいい.

コード


(2386.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
typedef long long ll;
typedef vector<int> vi;

int main(){
    int n;
    cin >> n;
    vector<vi> c(n,vi(n));
    rep(i,n) rep(j,n) cin >> c[i][j];
    ll ans = 0;
    rep(i,n) rep(j,i) ans += min(c[i][j], c[j][i]);
    cout << ans << endl;
}

Comments