ABC022_C - メモ的な何か

頂点1を含まないグラフを考えてその最短経路を作れば良いと思ったが
頂点1を含まないグラフの作り方 == 頂点1に隣接している頂点の選び方O(N^2)
dijkstra法O(N^2)
よって全体でO(N^4)掛かってしまい案の定TLEだった.

#include <bits/stdc++.h>
using namespace std;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
static const int INF = 1<<21;
static const int MAX_N = 300;
static const int MAX_M = 45000;
int n,m;
int res = INF;
int u[MAX_M],v[MAX_M],l[MAX_M];
int M[MAX_N][MAX_N];
int color[MAX_N],d[MAX_N];

void dijkstra(int s){//最短経路を求める
    int mincost;
    //初期化：全ての頂点uに対してcolor[u]をWHITE,d[u]をINF,d[s]=0,p[s]=-1;
    for(int u=0;u<n;u++){
        color[u] = WHITE;
        d[u] = INF;
    }
    d[s] = 0;
    color[s] = GRAY;

    while(1){
        mincost = INF;
        int u = -1;
        for(int i=0;i<n;i++){
            if(color[i]!=BLACK && d[i]<mincost){
                mincost = d[i];
                u = i;
            }
        }
        if(u==-1){
            break;
        }
        color[u] = BLACK;
        for(int v=0;v<n;v++){
            if(color[v]!=BLACK && M[u][v]!=INF){
                if(d[v]>d[u]+M[u][v]){
                    d[v] = d[u]+M[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>u[i]>>v[i]>>l[i];//家u[i]から家v[i]までの距離がl[i]
    }
    //隣接グラフにする
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            M[i][j] = INF;
        }
    }
    for(int i=0;i<m;i++){
        M[u[i]-1][v[i]-1] = l[i];
        M[v[i]-1][u[i]-1] = l[i];
    }
    //始点1に隣接する接点を2つ選ぶ
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(M[0][i]!=INF && M[0][j]!=INF){//始点に2つ隣接する頂点があったら
                int tmp1 = M[0][i];
                int tmp2 = M[0][j];
                M[0][i] = INF;
                M[0][j] = INF;
                dijkstra(i);
                res = min(res,tmp1 + tmp2 + d[j]);
                M[0][i] = tmp1;
                M[0][j] = tmp2;
            }
        }
    }
    if(res==INF)res = -1;
    cout<<res<<endl;
    return 0;
}

そこでwarshall_froyd法を用いた.
warshall_floyd法はグラフの全ての頂点の間の最短路を見つけるアルゴリズム.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<vector<int> > Matrix;

const int INF = 1<<21;
Matrix d;//隣接行列

void warshall_floyd(int n){//n：頂点数
    for(int i=0;i<n;i++){//経由する頂点
        for(int j=0;j<n;j++){//開始頂点
            for(int k=0;k<n;k++){//終端
                d[j][k] = min(d[j][k],d[j][i] + d[i][k]);//j->kの経路がiを経由して短縮できたら更新する
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n;
    d = Matrix(n,vector<int>(n,INF));//n*n行列,要素はINF
    for(int i=0;i<n;i++){
        d[i][i] = 0;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        int from,to,cost;
        cin>>from>>to>>cost;
        d[from][to] = cost;
        d[to][from] = cost;
    }

    warshall_floyd(n);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j && d[i][j]!=INF){
                cout<<i<<"から"<<j<<"へのコスト："<<d[i][j]<<endl;
            }
        }
    }
    return 0;
}

最短経路問題（ベルマンフォード法・ワーシャルフロイド法） - アルゴリズム講習会
abc022.contest.atcoder.jp
解答

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
static const int MAX_N = 300;
typedef vector<vector<int> > Matrix;

const int INF = 1<<29;
Matrix d;//隣接行列

void warshall_floyd(int n){//n：頂点数
    for(int i=1;i<n;i++){//経由する頂点
        for(int j=1;j<n;j++){//開始頂点
            for(int k=1;k<n;k++){//終端
                d[j][k] = min(d[j][k],d[j][i] + d[i][k]);//j->kの経路がiを経由して短縮できたら更新する
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n;
    d = Matrix(n,vector<int>(n,INF));//n*n行列,要素はINF
    for(int i=0;i<n;i++){
        d[i][i] = 0;
    }
    cin>>m;
    for(int i=0;i<m;i++){
        int from,to,cost;
        cin>>from>>to>>cost;
        d[from-1][to-1] = cost;
        d[to-1][from-1] = cost;
    }

    //WFで頂点1以外の最短経路を更新
    warshall_floyd(n);

    //頂点1から隣接した2点に
    int res = INF;
    for(int i=1;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            res = min(res,d[0][i]+d[0][j]+d[i][j]);
        }
    }
    cout<<(res!=INF?res:-1)<<endl;
    return 0;
}