Submission #4033310


Source Code Expand

#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

static const ll MAX = 201; // number of vertex
static const ll INF = mop;
static const ll whi = 0;
static const ll gra = 1;
static const ll bla = 2;

ll n, adj[MAX][MAX]; // adjacency matrix
ll d[MAX][MAX];

void dijkstra(ll k){
    ll minv;
    ll color[MAX];

    for (ll i=1;i<=n;i++){
        d[k][i] = INF;
        color[i] = whi;
    }

    d[k][k] = 0; // starting point distance
    color[k] = gra;
    while(true){
        minv = INF;
        ll u = -1;
        for (ll i=1;i<=n;i++){
            if(minv > d[k][i] and color[i] != bla){
                u = i;
                minv = d[k][i];
            }
        }
        if(u == -1){
            break;
        }
        color[u] = bla;
        for (ll v=1;v<=n;v++){
            if(color[v] != bla and adj[u][v] != INF){
                if(d[k][v] > d[k][u] + adj[u][v]){
                    d[k][v] = d[k][u] + adj[u][v];
                    color[v] = gra;
                }
            }
        }
    }
}


int main() {
   
    ll m,r;
    cin >> n >> m >> r;
    vector <ll> des;
    for (ll i=0;i<r;i++){
        ll x;
        cin >> x;
        des.push_back(x);
    }
    for (ll i=1;i<=n;i++){
        for (ll j=1;j<=n;j++){
            adj[i][j] = INF;
        }
    }
    for(ll i=0;i<m;i++){
        ll a,b,c;
        cin >> a >> b >> c;
        adj[a][b] = c;
        adj[b][a] = c;
    }
//    for (ll i=1;i<=n;i++){
//        if(i-1){
//            cout << endl;
//        }
//        for(ll j=1;j<=n;j++){
//            cout << adj[i][j] << " ";
//        }
//    }
//    cout << endl;
    for (ll i=1;i<=n;i++){
        dijkstra(i);
    }

    ll ans = INF;
    do{
        ll pre = 0;
        for (ll i=0;i<r-1;i++){
            pre += d[des[i]][des[i+1]];
        }
        if(ans > pre){
            ans = pre;
        }
    }while(next_permutation(des.begin(), des.end()));

    cout << ans << endl;
//    for (ll i=1;i<=n;i++){
//        for (ll j=1;j<=n;j++){
//            cout << i << " " << j << " " << d[i][j] << endl;
//        }
//    }



}


Submission Info

Submission Time
Task D - joisino's travel
User KFCHY
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2574 Byte
Status WA
Exec Time 54 ms
Memory 896 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 10
WA × 1
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
01.txt AC 54 ms 896 KB
02.txt AC 37 ms 896 KB
03.txt AC 35 ms 896 KB
04.txt AC 45 ms 896 KB
05.txt AC 53 ms 896 KB
06.txt WA 54 ms 896 KB
07.txt AC 34 ms 896 KB
08.txt AC 21 ms 896 KB
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB