第七回情報オリンピック予選 Ｆ 船旅 の計算量改善

実現したいこと

第七回情報オリンピック予選 Ｆ　船旅　の計算量改善

前提

この問題をダイクストラ法で解こうとして一応解けましたがほかの人と比べて明らかに実行時間が長くなってしまっていたのでそこを改善したい

該当のソースコード

c++

12#define _GLIBCXX_DEBUG3#include <bits/stdc++.h>4#define rep(i, v) for (int i = 0; i < (int)(v); i++)5#define REP(i,n,m) for(int i=(int)n;i<(int)m;i++)6#define fi first 7#define se second 8#define pb push_back9#define mp make_pair10#define all(o) (o).begin(), (o).end()11#define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}12#define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}13#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}14#define vvi vector<vector<int>> 15#define vvl vector<vector<ll>>16#define vi vector<int>17#define vl vector<ll> 18#define vs vector<string>19#define vvvi vector<vvi>20#define vc vector<char>21#define vvc vector<vector<char>>22#define vb vector<bool>23#define vvb vector<vector<bool>> 24#define vs vector<string>25#define vvs vector<vs>26#define pque priority_queue27#define unma unordered_map28#define unse unordered_set29#define smpq(n) priority_queue<n,vector<n>,greater<n>>30using namespace std;31using ll = long long;32using ull = unsigned long long;33using pii = pair<int, int>;34using pll = pair<ll, ll>;35template<typename T> inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }36 37const int inf = (1LL << 31) - 1;38const ll INF = (1LL << 61) - 1;39int main() {40 int n, k;41 cin >> n >> k;42 vector<vector<pll>> d(n, vector<pll>());43 while (k--) {44 int l;45 cin >> l;46 if (l == 0) {47 int a, b;48 int g = 0;49 cin >> a >> b;50 51 vl dis(n, INF);52//頂点iにたどり着ける最短距離53 smpq(pii) que;54 que.push(pii(0, a - 1));55 dis[a - 1] = 0;56 while (que.size()) {57 pll p = que.top();58 que.pop();59 60　　　　　　　　　//ゴール61 if (p.se == b - 1) {62 cout << dis[b - 1] << '\n';63 g++;//フラグ管理64 break;65 }66 if (p.fi > dis[p.se])67 continue;68 69 //いけるところで距離が更新できるところだけqueに入れる70 for (auto x : d[p.se]) {71 if (dis[x.se] > p.first + x.fi) {72 que.push(pll(p.fi +x.fi, x.se));73 dis[x.se] = p.first + x.fi;74 }75 }76 }77 if (!g)78 cout << -1 << '\n';79 80 }81 else {82 ll c, d, e;83 cin >> c >> d >> e;84 d[c - 1].pb(pll(e,d-1));85 d[d - 1].pb(pll(e, c-1));86 }87 }88}89 90

試したこと

ほかの人の提出をみてそれに実装を似せたりするも効果がなかったです
queの内部処理もいろいろ試してみるも同じでした

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。