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