いわゆる拡張ダイクストラの実装

JOIいっぱい解いてこのタイプの問題（いわゆる拡張ダイクストラ？）になれたから慣れてるうちにメモ。
下の問題はこれ

• C++17以降ならタプルの構造化束縛を使うと楽（array を使ったほうが楽です 2022/7/3 改定）
• グリッドグラフは辺を陽に持たなくていい
• continue使った方が{}のネストが小さくなって好き
• resもdijkstra中に最小値を探した方があとあと楽（誤差？）

あと一般グラフでも今まで頂点に辺を持たせていたけど、辺リストを作った方が楽かもと思い始めてる。
正直シンタックスハイライトがしてみたいからこの記事を書いたみたいなところある。
あとこの記事で初めてはてな記法使ったけど、こっちの方が書きやすくて良いですね。

#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<climits>
using namespace std;
int inf=INT_MAX;
int main(){
    int h,w;cin>>h>>w;
    vector<vector<int>> a(h,vector<int>(w,0));
    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            cin>>a[i][j];
        }
    }
    vector<vector<vector<int>>> dp(h,vector<vector<int>>(w,vector<int>(h*w+1,inf)));
    dp[0][0][0]=0;
    priority_queue<tuple<int,int,int,int>,vector<tuple<int,int,int,int>>,greater<tuple<int,int,int,int>>> que;
    que.push({0,0,0,0});
    vector<int> dx={1,0,-1,0};
    vector<int> dy={0,-1,0,1};
    int res=inf;
    while(!que.empty()){
        auto [time,yy,xx,dist]=que.top();que.pop();
        if(dist==h*w)continue;
        for(int i=0;i<4;++i){
            int y=yy+dy[i];
            int x=xx+dx[i];
            if(y<0||y>=h)continue;
            if(x<0||x>=w)continue;
            if(dp[y][x][dist+1]>time+a[y][x]*(dist*2+1)){
                dp[y][x][dist+1]=time+a[y][x]*(dist*2+1);
                que.push({dp[y][x][dist+1],y,x,dist+1});
                if(y==h-1&&x==w-1)res=min(res,dp[y][x][dist+1]);
            }
        }
    }
    cout<<res<<"\n";
    return 0;
}