九度OJ-1162：I Wanna Go Home

　　使用的依然是Dijkstra算法的模闆。略作修改即可

題目描述：

    The country is facing a terrible civil war----cities in the country are divided into two parts supporting different leaders. As a merchant, Mr. M does not pay attention to politics but he actually knows the severe situation, and your task is to help him reach home as soon as possible. 

    "For the sake of safety,", said Mr.M, "your route should contain at most 1 road which connects two cities of different camp."

    Would you please tell Mr. M at least how long will it take to reach his sweet home?

輸入：

    The input contains multiple test cases.

    The first line of each case is an integer N (2<=N<=600), representing the number of cities in the country.

    The second line contains one integer M (0<=M<=10000), which is the number of roads.

    The following M lines are the information of the roads. Each line contains three integers A, B and T, which means the road between city A and city B will cost time T. T is in the range of [1,500].

    Next part contains N integers, which are either 1 or 2. The i-th integer shows the supporting leader of city i. 

    To simplify the problem, we assume that Mr. M starts from city 1 and his target is city 2. City 1 always supports leader 1 while city 2 is at the same side of leader 2. 

    Note that all roads are bidirectional and there is at most 1 road between two cities.

Input is ended with a case of N=0.

輸出：

    For each test case, output one integer representing the minimum time to reach home.

    If it is impossible to reach home according to Mr. M's demands, output -1 instead.

樣例輸入：

2
1
1 2 100
1 2
3
3
1 2 100
1 3 40
2 3 50
1 2 1
5
5
3 1 200
5 3 150
2 5 160
4 3 170
4 2 170
1 2 2 2 1
0      

樣例輸出：

100
90
540      

來源：

2011年北京大學計算機研究所學生機試真題

答疑：

解題遇到問題?分享解題心得?讨論本題請通路： http://t.jobdu.com/thread-7885-1-1.html

#include <iostream>
#include <vector>
#define MAXSIZE 600 
#define MAXSIZE_EDGE 10000
using namespace std;
struct Edge{
	int start,end;
	double weight;
	Edge(){
	}
	Edge(int start,int end,double weight){
		this->start=start;
		this->end=end;
		this->weight=weight;
	}
	bool operator<(const Edge e){//useless
		return weight<e.weight;
	}
}; 

struct Vex{
	int root;
	Vex(){//initiate root
		this->root=-1;
	} 
};
struct Graph{ //頂點下标從0開始 
	int graphSize;
	vector<Edge> edge[MAXSIZE_EDGE];
	int initGraph(int graphSize){
		this->graphSize=graphSize;
		for (int i=0;i<graphSize;i++)
			edge[i].clear();
	}
};
int main(){
	int n,m;
	Graph graph;
	int start,end,weight;
	bool mark[MAXSIZE];
	int dist[MAXSIZE];
	int conversion[MAXSIZE]; 
	int support[MAXSIZE];
	int newPoint,minDistVex;
	int temp,tempCon;
	while (cin>>n,n){//n vexes ,m edges
		cin>>m;
		//initiate
		graph.initGraph(n);
		newPoint=0;//originate 0
		for (int i=0;i<graph.graphSize;i++){
			mark[i]=false;
			dist[i]=-1;
			conversion[i]=0;
		}
		mark[newPoint]=true;
		dist[newPoint]=0;
		//input edge&&support
		for (int i=0;i<m;i++){
			cin>>start>>end>>weight;
			start--;end--;
			graph.edge[start].push_back(Edge(start,end,weight));
		 
			graph.edge[end].push_back(Edge(end,start,weight));
		
		}
		for (int i=0;i<graph.graphSize;i++){
			cin>>support[i];
		}
		//process
		for (int time=0;time<n-1;time++){//每趟循環找出x到一個結點的最短路徑,共n-1趟 
			//周遊newPoint直接相鄰的結點，修改其dist
			for (int i=0;i<graph.edge[newPoint].size();i++){
				int end=graph.edge[newPoint][i].end;
				if (mark[end]==true)//if end結點已經在x集合中，則跳過此次循環 
					continue;
				tempCon=conversion[newPoint]+(support[end]==support[newPoint]?0:1);//if 轉向将要大于一次 continue 
				if (tempCon>1)
					continue;
				temp=dist[newPoint]+graph.edge[newPoint][i].weight;
				if (temp<dist[end]||dist[end]==-1) {//if the new dist< the old dist,modify the path
					dist[end]=temp;
					conversion[end]=tempCon;
				}
			}	
			//周遊dist，從mark為false的結點中找出其dist最小的結點，确定為新的newPoint，并加入x集合 
			int i;
			for (i=0;i<graph.graphSize;i++){//initiate minDistVex
				if (mark[i]==false&&dist[i]!=-1){
					minDistVex=i;
					break;
				}
			}
			for (i++;i<graph.graphSize;i++){
				if (mark[i]==false&&dist[i]!=-1&&dist[i]<dist[minDistVex])
					minDistVex=i;
			} 
			newPoint=minDistVex;
			mark[minDistVex]=true;
		} 
		//output. output dist[]
			cout<<dist[1]<<endl;
		
	}
	return true;
}