2020年 6月 20日
まえがき
朝、それはつまり・・・・ 朝
健康管理
昨日の昼に大学で買ってきた豚丼を今食ってます。
お腹が重たい…
寝るわ
何した
具体的に
今日解いた問題
ABC022 C- Blue Bird
- [天才パズル,ワーシャルフロイド法,全点対間最短距離,閉路から経路]
これ面白いですね。天才パズルコンだ。
僕はBFSで解こうとしました…(駄目でした)
距離が短くなった時だけまたpushする、みたいにやってたんですけど、ソレだとゴールに到着出来ない、的なことが起きてて泣いてました。
想定解法が賢すぎる。
閉路に対して、ある頂点を1個除いてやれば、辺の数が2個減った経路になる。
vector<P> graph[100100]; int main() { int n, m; cin >> n >> m; vector<P> zer(0); vector<vector<ll>> d(n,vector<ll> (n,1e9)); rep(i,m){ int x, y, l; cin >> x >> y >> l; --x, --y; if(x==0){ //頂点0(高橋くんの家)と繋がっている点だけ別に保持しておく zer.push_back({y,l}); } else { d[x][y] = l; d[y][x] = l; } } // ワーシャルフロイド法 vector<ll> dist(n,1e9); rep(i,n){ d[i][i] = 0; // これなくてもAC まじ? } for (int k = 1; k < n; k++){ for(int i = 1; i < n; i++){ for(int j = 1; j < n; j++){ chmin(d[i][j], d[i][k] + d[k][j]); } } } ll ans = 1e9; rep(i,zer.size()){ // 高橋君の家の家の隣にあって、最初に訪れる家と最後に訪れる家を全て試す For(j,i+1,zer.size()){ chmin(ans,d[zer[i].first][zer[j].first] + zer[i].second + zer[j].second); } } cout << (ans == 1e9? -1 : ans) << endl; //cout << ans << endl; }
あとがき
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)