[アルゴリズム]白駿4485
4281 ワード
質問する
質問リンク
これは多分野を体現する問題である.
しかし、最初は少し慌てていたのは.
以前は1210のように1->2で10ドルかかりました.形態的に複数の極端を示した.
問題は0,0からn−1,n−1まで距離を求めることである.
したがって,上記のグラフでは9つのノードが存在し,各ノードに移動するコストが考えられる.
また、多出口の最小料金幹線の抜去を継続するため、優先行列を利用した.
pythonはheapとして使用し、c++はqueueと同様にpriority queueが存在する.
メンバー関数としてfrontの代わりにtopを使用します.(上のみ)
また、defaultなので、一番小さいお尻を使いたいなら-.
code /**
* 백준 4485
* 다익스트라
* 최소 스패닝 트리
*/
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
int n;
vector<vector<int>> graph;
vector<vector<int>> d;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
void dijkstra(){
priority_queue<vector<int>> que;
// cost,now_y,now_x
int sY=0,sX=0;
que.push({-graph[sY][sX],sY,sX});
d[sY][sX]=graph[sY][sX];
while(!que.empty()){
vector<int> now = que.top();
que.pop();
int nC=-now[0];
int nY=now[1];
int nX=now[2];
// 현재거리가 더 짧다면 검사 x
if(d[nY][nX]<nC){continue;}
// 인접 노드 거리 체크
for(int i=0;i<4;i++){
int mY=nY+dy[i];
int mX=nX+dx[i];
// 범위
if(mY<0 || mY>=n || mX<0 || mX>=n) continue;
// 현재 거리보다 경유하는게 더짧다면 갱신
int newDist=d[nY][nX]+graph[mY][mX];
if(newDist<d[mY][mX]){
d[mY][mX]=newDist;
que.push({-newDist,mY,mX});
}
}
}
}
int main(void){
int tc=0;
while(true){
cin>>n;
if(n==0){
break;
}
// init graph
graph.clear();
for(int i=0;i<n;i++){
vector<int> tmp;
tmp.clear();
for(int j=0;j<n;j++){
int a;
scanf("%d",&a);
tmp.push_back(a);
}
graph.push_back(tmp);
}
// init distance
d.clear();
for(int i=0;i<n;i++){
vector<int> tmp;
tmp.clear();
for(int j=0;j<n;j++){
tmp.push_back(INF);
}
d.push_back(tmp);
}
// call dijkstra
dijkstra();
cout<<"Problem "<<++tc<<": "<<d[n-1][n-1]<<endl;
}
}
Reference
この問題について([アルゴリズム]白駿4485), 我々は、より多くの情報をここで見つけました
https://velog.io/@shininghyunho/알고리즘-백준-4485
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
/**
* 백준 4485
* 다익스트라
* 최소 스패닝 트리
*/
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
int n;
vector<vector<int>> graph;
vector<vector<int>> d;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
void dijkstra(){
priority_queue<vector<int>> que;
// cost,now_y,now_x
int sY=0,sX=0;
que.push({-graph[sY][sX],sY,sX});
d[sY][sX]=graph[sY][sX];
while(!que.empty()){
vector<int> now = que.top();
que.pop();
int nC=-now[0];
int nY=now[1];
int nX=now[2];
// 현재거리가 더 짧다면 검사 x
if(d[nY][nX]<nC){continue;}
// 인접 노드 거리 체크
for(int i=0;i<4;i++){
int mY=nY+dy[i];
int mX=nX+dx[i];
// 범위
if(mY<0 || mY>=n || mX<0 || mX>=n) continue;
// 현재 거리보다 경유하는게 더짧다면 갱신
int newDist=d[nY][nX]+graph[mY][mX];
if(newDist<d[mY][mX]){
d[mY][mX]=newDist;
que.push({-newDist,mY,mX});
}
}
}
}
int main(void){
int tc=0;
while(true){
cin>>n;
if(n==0){
break;
}
// init graph
graph.clear();
for(int i=0;i<n;i++){
vector<int> tmp;
tmp.clear();
for(int j=0;j<n;j++){
int a;
scanf("%d",&a);
tmp.push_back(a);
}
graph.push_back(tmp);
}
// init distance
d.clear();
for(int i=0;i<n;i++){
vector<int> tmp;
tmp.clear();
for(int j=0;j<n;j++){
tmp.push_back(INF);
}
d.push_back(tmp);
}
// call dijkstra
dijkstra();
cout<<"Problem "<<++tc<<": "<<d[n-1][n-1]<<endl;
}
}
Reference
この問題について([アルゴリズム]白駿4485), 我々は、より多くの情報をここで見つけました https://velog.io/@shininghyunho/알고리즘-백준-4485テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol