#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<memory.h>
#include<fstream>
using namespace std;
const int INF = 1<<29;
const int nMax = 10000;
struct edge{
	edge(){}
	edge(int x,int y){
		cost = x;
		to = y;
	}
	bool operator<(const edge& rhs)const{
		return cost > rhs.cost;
	}
	int cost ;
	int to;
};
vector<edge> node[nMax];

int dist1[nMax];
int dist2[nMax];


void dijkstra(int s){

	for (int i = 0;i<nMax;++i)
		dist1[i] = INF;
	
	for (int i = 0;i<nMax;++i)
		dist2[i] = INF;	
	
	dist1[s] = 0;
	priority_queue<edge,vector<edge>> q;
	q.push( edge(0,s));
	edge u ;
	while (!q.empty())
	{

		u = q.top();q.pop();
		int sz = node[u.to].size();
		int v = u.to;
		if (u.cost > dist2[v])
			continue;

		for (int i = 0;i<sz;++i)
		{
				int next = node[v][i].to;
				int d = node[v][i].cost + u.cost;

				if (d < dist1[next])
				{
					swap(d,dist1[next]);
					q.push(edge(dist1[next],next));
				}
				if (d > dist1[next] && d < dist2[next])
				{
					dist2[next] = d;
					q.push(edge(dist2[next],next));
				}	
		}

	}
	
}


int main(){
	
	//FILE *p = freopen("data.txt","r",stdin);
	int n,r;
	cin >> n >> r;
	int x,y,cost;
	for (int i = 0;i<r;++i){
		cin >> x >>y >> cost;
		node[x].push_back( edge(cost,y));
		node[y].push_back( edge(cost,x));
	}

	dijkstra(1);
	printf("%d\n",dist2[n]);
	//fclose(p);

}

• Re:贴份代码 (9) count_if 2015-05-11 17:50:10
  • Re:贴份代码 (11) dongnanfeng 2015-05-15 14:43:37