ダイクストラ

vector<vector<pair<int,int»>の形のグラフを投入

v[i]にあるvector<pair<int,int»をpとしたときpにはiからの{行き先、距離}を記録する

ds(グラフ,スタート地点)

スタート視点からの距離が記録されたvectorが帰ってくる

負の重みを持つ辺を入れてはいけない

vector<long long> ds(vector<vector<pair<long long,long long>>>& v,long long str){
    long long inf = 1e9;
    vector<long long> ans(v.size(),inf);
    ans[str] = 0;
    priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> q;
    q.push({0,str});
    while(q.size()!=0){
        long long cos = q.top().first;
        long long pos = q.top().second;
        q.pop();
        if(cos > ans[pos])continue;
        for(pair<long long,long long> i : v[pos]){
            if(ans[i.first] > cos + i.second){
                ans[i.first] = cos + i.second;
                q.push({cos+i.second,i.first});
            }
        }
    }
    return ans;
}