ZJ d793: 00929 - Number Maze

題目鏈接:https://zerojudge.tw/ShowProblem?problemid=d793

dijkstra最短路

二維就開個二維去存

要注意第一個點的值也要算進去,一開始沒發現還WA了

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

struct node

{

ll x,y,val;

vector<pair<ll,ll>> child;

};

int main()

{

AC

ll t,n,m;

cin>>t;

while(t--)

{

cin>>n>>m;

vector<vector<node>> v(n+1,vector<node>(m+1));

vector<vector<ll>> dis(n+1,vector<ll>(m+1,1e9));

for(ll i=1;i<=n;i++)

for(ll j=1;j<=m;j++)

{

cin>>v[i][j].val;

if(i-1) v[i][j].child.emplace_back(i-1,j),v[i-1][j].child.emplace_back(i,j);

if(j-1) v[i][j].child.emplace_back(i,j-1),v[i][j-1].child.emplace_back(i,j);

}

std::priority_queue<tuple<ll,ll,ll>> pq;

pq.emplace(dis[1][1]=v[1][1].val,1,1);

while(pq.size())

{

ll val,x,y;

tie(val,x,y)=pq.top();

if(x==n&&y==m) break;

pq.pop();

for(auto e:v[x][y].child)

{

if(dis[e.first][e.second]>dis[x][y]+v[e.first][e.second].val)

{

dis[e.first][e.second]=dis[x][y]+v[e.first][e.second].val;

pq.emplace(-dis[e.first][e.second],e.first,e.second);

}

}

}

cout<<dis[n][m]<<'\n';

}

}