hdu 2544 최 단 로 Dijstra 알고리즘 더미 최적화, Bellman - ford, Bellman - ford 대기 열 최적화

최 단 로
Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 48071    Accepted Submission(s): 21174
Problem Description
매년 학교 경기 에서 결승전 에 진출 하 는 모든 학우 들 은 매우 아름 다운 t - shirt 를 받는다.하지만 우리 스 태 프 들 이 수백 벌 에 달 하 는 옷 을 상점 에서 경기장 으로 옮 길 때마다 매우 피곤 하 다!그래서 지금 그들 은 가장 짧 은 상점 에서 경기장 까지 의 노선 을 찾 으 려 고 하 는데, 당신 은 그들 을 도와 줄 수 있 습 니까?
 
Input
여러 그룹의 데 이 터 를 입력 하 십시오.각 조 의 데이터 첫 줄 은 두 개의 정수 N, M (N & lt; 100, M & gt; = 10000) 이 고 N 은 청 두 의 거리 에 몇 개의 길목 이 있 고 1 로 표 시 된 길목 은 상점 소재지 이 며 N 으로 표 시 된 길목 은 경기장 소재지 이 며 M 은 청 두에 몇 개의 길이 있다 고 표시 한다.N = M = 0 은 입력 이 끝 났 음 을 나타 낸다.다음 M 줄 은 각 줄 에 3 개의 정수 A, B, C (1 & lt; = A, B & gt; = N, 1 & gt; = C & gt; = 1000) 를 포함 하여 길목 A 와 길목 B 사이 에 길이 있다 는 것 을 나타 내 고 우리 직원 들 은 C 분 의 시간 이 이 길 을 걸 어야 한다.
적어도 한 개의 상점 이 경기장 으로 가 는 노선 을 입력 하 세 요.
 
Output
각 조 의 수입 에 대해 한 줄 을 수출 하 는 것 은 직원 들 이 상점 에서 경기장 으로 가 는 가장 짧 은 시간 을 나타 낸다.
 
Sample Input

   
   
   
   

    
    
    
    2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
2
   
   
   
   

Dijstra 더미 최적화 알고리즘

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <queue>
#include <vector>
#include <limits>

using namespace std;

const int maxn = 150;
const int INF = numeric_limits<int>::max();

struct Edge {
	int from, to, dist;
	Edge(int from, int to, int dist) : from(from), to(to), dist(dist) {}
};

struct HeapNode {
	int d, u;
	HeapNode(int d, int u) : d(d), u(u) {}
	bool operator < (const HeapNode& hns) const {
		return d > hns.d;
	}
};

struct Dijstra {
	int d[maxn], p[maxn], n;
	bool v[maxn];
	vector<Edge> edges;
	vector<int> G[maxn];

	void Init(int n) {
		this->n = n;
		edges.clear();
		for (int i = 0; i < n; i++) G[i].clear();
		for (int i = 0; i < n; i++) d[i] = INF;
		memset(v, false, sizeof(v));
	}

	void AddEdges(int from, int to, int dist) {
		int m;
		edges.push_back(Edge(from, to, dist));   // edges      G 
		m = edges.size();
		G[from].push_back(m - 1);

		edges.push_back(Edge(to, from, dist));
		m = edges.size();
		G[to].push_back(m - 1);
	}

	void dijstra(int s) {
		d[s] = 0;
		priority_queue<HeapNode> Q;
		Q.push(HeapNode(0, s));
		while (!Q.empty()) {
			HeapNode hn = Q.top(); Q.pop();
			int u = hn.u;
			if (v[u]) continue;
			v[u] = true;
			for (int i = 0; i < G[u].size(); i++) {
				Edge& e = edges[G[u][i]];
				if (d[e.to] > d[e.from] + e.dist) {
					d[e.to] = d[e.from] + e.dist;
					p[e.to] = G[u][i];
					//push()
					Q.push(HeapNode(d[e.to], e.to));
				}
			}
		}
	}

};

int main()
{
	int N, M;
	Dijstra dij;
	while (~scanf("%d%d", &N, &M) && (N || M)) {
		dij.Init(N);
		int from, to, dist;
		for (int i = 0; i < M; i++) {
			scanf("%d%d%d", &from, &to, &dist);
			dij.AddEdges(from - 1, to - 1, dist);
		}
		dij.dijstra(0);
		printf("%d
", dij.d[N - 1]);
	}
	return 0;
}

벨 맨 - 포드 알고리즘
만약 최 단 로 가 존재 한다 면, 반드시 고리 가 없 는 최 단 로 가 존재 할 것 이다.
이 유 는 다음 과 같다.0 링 이나 정 링 이 포함 되 어 있 으 면 제거 후 경로 가 길 지 않 습 니 다.
네 거 티 브 링 을 포함 하면 가장 짧 은 길이 가 존재 하지 않 는 다 는 것 을 의미 합 니 다. 네 거 티 브 링 에서 한 번 돌 때마다 경로 의 길 이 를 줄 이 고 최소 값 이 없 기 때 문 입 니 다.
링 이 없 는 이상 가장 짧 은 경 로 는 n - 1 개의 정점 만 거 쳐 n - 1 '라운드' 이완 을 통 해 얻 을 수 있 습 니 다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 10005 * 2;  //   ，    
const int INF = numeric_limits<int>::max();

int u[maxn], v[maxn], w[maxn], d[105];
int N, M;

int main()
{
	while (~scanf("%d%d", &N, &M) && (N || M)) {

		for (int i = 1; i <= N; i++) d[i] = INF;

		for (int i = 1; i <= M; i++) {
			scanf("%d%d%d", &u[i], &v[i], &w[i]);
		}
		for (int i = M + 1; i <= M + M; i++) {
			u[i] = v[i - M];
			v[i] = u[i - M];
			w[i] = w[i - M];
		}
		d[1] = 0;
		for (int i = 0; i < N - 1; i++) {
			for (int k = 1; k <= M + M; k++) {
				int x = u[k], y = v[k];
				if (d[x] < INF) {
					d[y] = min(d[y], d[x] + w[k]);  //  
				}
			}
		}
		printf("%d
", d[N]);
	}
	return 0;
}

시간 복잡 도 O (n * m)
대기 열 로 Bellman - ford 알고리즘 을 최적화 하고 인접 표 로 그림 을 저장 하여 변 에 대한 중복 검 사 를 감소 합 니 다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
const int maxn = 10005 * 2;
const int INF = numeric_limits<int>::max();
struct Edge {
	int u, v, w;
	Edge(int u, int v, int w) : u(u), v(v), w(w) {};
	Edge() {};
};

int d[105];
int N, M;
bool inq[105];  //        queue 
queue<int> Q;
vector<int> G[105];
vector<Edge> edges;

int main()
{
	while (~scanf("%d%d", &N, &M) && (N || M)) {
		//init
		for (int i = 1; i <= N; i++) d[i] = INF;
		memset(inq, false, sizeof(inq));
		edges.clear();
		for (int i = 1; i <= N; i++) G[i].clear();
		while (!Q.empty()) Q.pop();

		for (int i = 1; i <= M; i++) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);

			edges.push_back(Edge(u, v, w));
			G[u].push_back(edges.size() - 1);

			edges.push_back(Edge(v, u, w));  //   ，       
			G[v].push_back(edges.size() - 1);
		}

		d[1] = 0;
		inq[1] = true;
		Q.push(1);

		//bellman-ford    ，          
		while (!Q.empty()) {
			int p = Q.front(); Q.pop();
			inq[p] = false;

			//                 ，                
			for (int i = 0; i < G[p].size(); i++) {
				Edge& e = edges[G[p][i]];
				if (d[p] < INF && d[p] + e.w < d[e.v]) {
					d[e.v] = d[p] + e.w;
					if (!inq[e.v]) {
						Q.push(e.v);
						inq[e.v] = true;
					}
				}
			}
		}

		printf("%d
", d[N]);
	}
	return 0;
}