九度 1545：奇怪的连通图

题目描述

总结

1. 用 BFS 实现 Dijkstra. 要点是, visited 后标记, 把某个点从优先队列取出后再标记

代码 未通过九度测试 RE

/*
 * source.cpp
 *
 *  Created on: 2014-4-4
 *      Author: vincent
 */

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;

class GraphNode {
public:
	int index;
	int dis;
	GraphNode(int _index, int _dis):index(_index), dis(_dis) {
	}
	GraphNode() {
		GraphNode(0, 0);
	}
};

class QueueNode {
public:
	int index;
	int dis;
	QueueNode(int _index, int _dis):index(_index), dis(_dis) {}
	QueueNode() {
		QueueNode(0, 0);
	}
	bool operator <(const QueueNode &other) const {
		return this->dis > other.dis;
	}
};
const int INF = 0X3F3F3F3F;
vector<GraphNode> graph[10100];
bool visited[10100];

int main() {
	int vertex, edge;
	freopen("input.txt", "r", stdin);

	while(scanf("%d%d", &vertex, &edge) != EOF) {
		for(int i = 0; i <= vertex; i++)
			graph[i].clear();

		memset(visited, 0, sizeof(visited));
		int m, n, k;
		for(int i = 0; i < edge; i ++) {
			scanf("%d%d%d", &m, &n, &k);
			graph[m].push_back(GraphNode(n, k));
			graph[n].push_back(GraphNode(m, k));
		}
		priority_queue<QueueNode> record;
		record.push(QueueNode(1, 0));
		visited[1] = true;

		int minK = INF;
		while(!record.empty()) {
			QueueNode qNode = record.top();
			record.pop();

			if(qNode.index == vertex) {
				minK = qNode.dis;
				visited[qNode.index] = 1;
				break;
			}

			int index = qNode.index;
			for(size_t i = 0; i < graph[index].size(); i ++) {
				int j = graph[index][i].index;
				if(visited[j])continue;

				record.push(QueueNode(j, max(qNode.dis, graph[index][i].dis)));
			}
		}

		if(visited[vertex] == 0) {
			printf("-1
");
		}else {
			printf("%d
", minK);
		}
	}
	return 0;
}

　　

SPFA Solution WA

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <deque>
#include <cstring>
#define MIN(x,y) (x)<(y)?(x):(y)
using namespace std;

class Node  {
public:
	int index;
	int cost;

	Node()  {
		index = cost = -1;
	}

	Node(int _index, int _cost):index(_index), cost(_cost) {}
};

vector<Node> graph[10010];
int dist[10010];


int spfa(int m)  {
	deque<int> record;
	memset(dist, 0x3f, sizeof(dist));
	set<int> visited;

	record.push_back(1);
	visited.insert(1);
	dist[1] = 0;

	while(!record.empty())  {
		int fat = record.front();
		record.pop_front();
		

		for(int i = 0; i < graph[fat].size(); i ++)  {
			Node child = graph[fat][i];
			int child_index = child.index;
			int child_cost = child.cost;

			if(max(dist[fat],child_cost) < dist[child_index]) {
				dist[child_index] = max(dist[fat], child_cost);

				if(visited.count(child_index)) continue;
				record.push_back(child_index);
				visited.insert(child_index);
			}
		}

	}

	if(dist[m] == 0x3f3f3f3f)
		return -1;
	return dist[m];

}

int main() {
	freopen("C:\Users\vincent\Dropbox\workplacce\joj\test.txt", "r", stdin);
	
	int m, n;
	while(scanf("%d%d", &m, &n) != EOF)  {
		for(int i = 1; i <= m; i ++)  {
			graph[i].clear();
		}

		int from, to, cost;
		for(int i = 0; i < n; i ++)  {
			scanf("%d%d%d", &from, &to, &cost);
			graph[from].push_back(Node(to, cost));
			graph[to].push_back(Node(from, cost));
		}

		int res = spfa(m);
		printf("%d
", res);
	}

	return 0;
}