dijkstra 알고리즘 차단 경로 구하기
1421 단어 도론
#include
#include
#include
#include
#include
using namespace std;
#define N 5005
#define INF 111111111 //
struct Edge{
int to ,w;
bool operator a.w;
}
};
priority_queue Q;
vector V[N];
int n, m;
int dis[N], dis2[N];
void init(){
for(int i = 1; i <= n; i++){
V[i].clear();
dis[i] = INF;
dis2[i] = INF;
}
}
int dijkstra(){ // dijkstra
dis[1] = 0;
Edge p, q, r;
p.to = 1, p.w = 0;
Q.push(p);
while(!Q.empty()){
p = Q.top();
Q.pop();
int u = p.to;
if(p.w > dis2[u])continue;
for(int i = 0; i < V[u].size(); i++){
q = V[u][i];
int to = q.to, d = q.w + p.w;
if(dis[to] > d){
swap(dis[to], d);
r.to = to, r.w = dis[to];
Q.push(r);
}
if(dis[to] < d && dis2[to] > d){
dis2[to] = d;
r.to = to, r.w = d;
Q.push(r);
}
}
}
return dis2[n];
}
int main(){
int a, b, w;
Edge p;
while(cin>>n>>m){
init();
for(int i = 0; i < m; i++){
scanf("%d%d%d", &a, &b, &w);
p.to = b;
p.w = w;
V[a].push_back(p);
p.to = a;
V[b].push_back(p);
}
int len = dijkstra();
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 3631 Shortest Path(Floyd + 플러그인)제목: n개의 점 m줄 테두리(단방향 테두리)와 q차 조작을 드리겠습니다. 처음에는 모든 점이 표시가 없습니다. 두 가지 조작이 있습니다. 1.0 x: x를 표시하고 가까이 표시한 경우 "ERROR! At point...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
