Submission #1517381

---

Source Code Expand

#include <bits/stdc++.h>
#define INF 1000000000

using namespace std;

int d[301][301];

int main()
{
    fill(d[0], d[301], INF);
    
    vector<int> fstep;
    int n, m;
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int u, v, l;
        cin >> u >> v >> l;
        d[u][v] = d[v][u] = l;
        if(u==1)
        {
            fstep.push_back(v);
        }
    }
    
    for(int k=2; k<=n; k++)
    {
        for(int i=2; i<=n; i++)
        {
            for(int j=2; j<=n; j++)
            {
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }
    int res = INF;
    
    while(!fstep.empty())
    {
        int j = fstep.back();
        fstep.pop_back();
        for(int i : fstep)
        {
            res = min(res, d[1][i] + d[i][j] + d[j][1]);
        }
    }
    
    cout << (res==INF ? -1 : res) << endl;
    
    return 0;
}

Submission Info

Judge Result