紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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;
}