master

分支 (1)

管理

管理

master

algorithm
/
P5122-Disjistra.cpp

#include <iostream>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

struct node{
	int id; //节点id
	int cw; // start点到该点的最小距离
	bool operator < ( const node & y ) const{ // 反向 < 操作符， 以逆转priority_queue的默认排序
        return y.cw < cw;
    }
};

struct edge{
	int v; // 终点ID ， 起点是记录第一条edge的edgesHead的序号
	int w; // 该边权值
	int next; // 同一起点的下一条边，如果没有下一条，该值为 -1 ， 目的是为了加快处理某个起点的所有边
};

priority_queue<node> pqq; // 去向 回向复用
int inf=0x6fffffff;

void dijstra(int start, int* dists, int n, edge* edges, int* edgeHeads){
	bool used[n]={0}; // 已经得到最小值的标志， 1 为已经得到

	dists[start] = 0;
	pqq.push((node){start, 0});

	while(!pqq.empty()){
		node minNode = pqq.top();
		pqq.pop();

//		cout<<"process: {id="<<minNode.id<<", cw="<<minNode.cw<<"}"<<endl;
		// 检查minNode是否已经得到最小dist
		if(used[minNode.id]) continue;
		used[minNode.id] = true;

		// 使用 minNode的所有edge来更新dists
		int u = minNode.id;
		int edgeIndex = edgeHeads[u];
		while(edgeIndex>=0){ // 最后一条边的next为-1
			edge &e = edges[edgeIndex];
//			cout<<"      handle edge"<<edgeIndex<<": "<<&edges[edgeIndex]<<": {v="<<edges[edgeIndex].v<<" w="<<edges[edgeIndex].w<<" next="<<edges[edgeIndex].next<<"}"<<endl;
			if(dists[u]+e.w<dists[e.v]){ // 借由 minNode到e.v点的距离更短，要更新并且将e.v点加入到queue中，等下一次处理之
//				cout<<"             select edge: {v="<<e.v<<" w="<<e.w<<" next="<<e.next<<"}"<<endl;
				dists[e.v] = dists[u]+e.w;
				pqq.push((node){e.v, dists[e.v]});
			}
			edgeIndex = e.next;
		}
	}
//	cout<<endl<<"===================="<<(start+1)<<" dist:"<<endl;
//	for(int i=0;i<n;i++) cout<<dists[i]<<" ";
//	cout<<endl<<"===================="<<endl;
}

int main(){
	// 1. init data from input
	int n,m,k;
	cin>>n>>m>>k;

    /*  edges与 edgeHeads 的配合来快速找到一个节点的所有边, 比如：

	    edges[1].v=3      ... edges[3].v=12     ... edges[99].v=102 ....
	            .next=3   ...         .next=99  ...          .next=-1 ....
	    edgeHeads[10] = 1

	    上面数据表示： 节点10 有3条edge分别到节点 3、12、102
	*/
	map<int, int> grasses;  // {v,w}
	edge edges[m*2];  // {v,w}
	int edgeHeads[n]; // edgeHeads[u] == last {v,w} of node u
	int dists[k+1][n]; // dists[0] N到其他点的最短路径， dists[i] 第i个草捆到到其他点的最短路径

	for(int i=0;i<n;i++){
		edgeHeads[i]=-1; // -1 为edge.next的完结标志位
		for(int j=0; j<k+1; j++)
			dists[j][i]=inf; // 由于是记录最小值， 所以初始化为最大值
	}

	int u,v,w;
	for(int i=0;i<m;i++){
		cin>>u>>v>>w;
		u--; v--;
		edges[i]=(edge){v, w, edgeHeads[u]}; // edgeHeads[u]现在为node u的上一条边序号
		edgeHeads[u] = i;  // 记住 node v的最后一条边的序号

		edges[m+i]=(edge){u, w, edgeHeads[v]}; // edgeHeads[u]现在为node u的上一条边序号
		edgeHeads[v] = m+i;  // 记住 node v的最后一条边的序号
//		cout<<"edge"<<i<<": "<<&edges[i]<<": v="<<edges[i].v<<" next="<<edges[i].next<<" edgeHeads["<<u<<"]="<<edgeHeads[u]<<endl;
	}
//			cout<<"      edge"<<n<<": "<<&edges[n]<<": {v="<<edges[n].v<<" w="<<edges[n].w<<" next="<<edges[n].next<<"}"<<endl;
	for(int i=0;i<k;i++){
		cin>>u>>w;
		u--;
		if(!grasses.count(u)){
			grasses[u]=w; // 对应的最短距离在 dists[i+1]中
		}else{
			grasses[u]=max(w,grasses[u]); // 重复时，取最大值
		}
	}

	// 2. dijstra  使用dijstra算法算正向单源点start
	int start = n-1;
//			cout<<"      edge"<<n<<": "<<&edges[n]<<": {v="<<edges[n].v<<" w="<<edges[n].w<<" next="<<edges[n].next<<"}"<<endl;
	dijstra(start, &dists[0][0], n, edges, edgeHeads);
	int distIndx = 0;
	for(map<int,int>::iterator it=grasses.begin(); it!=grasses.end();it++){
		distIndx++;
		dijstra(it->first, &dists[distIndx][0], n, edges, edgeHeads);
	}

	// 3. output
	for(int i=0;i<n-1;i++){
		bool isFound = false;
		if(dists[0][i]<inf){ // i节点可达
			distIndx = 0;
			for(map<int,int>::iterator it=grasses.begin(); it!=grasses.end();it++){
				distIndx++;
				if(it->first==i){ // i节点有草料
					cout<<1<<endl;
					isFound = true;
					break;
				}else
				{
					int gIndx = it->first;
					if(dists[distIndx][i]+dists[0][gIndx]-it->second < dists[0][i]){
						cout<<1<<endl;
						isFound = true;
						break;
					}
				}
			}
		}
		if(!isFound) cout<<0<<endl;
	}

	return 0;
}


/*
test1, expect 1 1 1
================
4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7

test2, expect 1
================
64 112 3
1 9 95
17 18 101
17 9 105
47 39 138
19 27 78
19 11 100
6 5 50
37 45 114
34 42 64
51 43 106
61 53 141
60 59 115
41 33 86
10 18 101
23 22 78
48 40 57
48 56 71
42 43 145
10 2 87
62 61 143
23 24 78
45 44 61
35 43 79
42 50 54
11 3 113
50 49 88
49 57 90
43 44 68
21 29 138
16 8 67
15 14 146
45 46 93
27 28 133
24 32 149
30 38 75
14 22 140
38 37 89
28 29 136
12 4 132
6 7 114
25 17 57
42 41 54
33 34 61
55 56 78
62 54 93
56 64 118
29 37 72
27 26 60
58 50 51
10 9 80
19 20 55
46 47 86
20 28 76
44 52 115
5 13 66
1 2 108
38 39 87
58 59 74
3 4 86
39 40 149
14 6 100
51 59 121
36 35 81
55 47 80
26 25 144
50 51 113
30 29 131
64 63 146
58 57 123
63 55 118
31 39 145
53 54 116
12 20 90
27 35 134
16 24 92
38 46 57
35 34 106
32 31 68
63 62 62
7 8 122
14 13 59
41 49 60
15 23 137
18 26 51
34 26 122
11 10 105
61 60 149
31 23 54
53 45 61
54 55 117
12 11 78
13 12 100
28 36 108
21 22 74
30 31 119
47 48 131
25 33 134
15 16 122
32 40 100
15 7 135
36 37 149
36 44 92
22 30 63
4 5 140
18 19 140
53 52 131
21 20 86
51 52 105
2 3 54
54 46 119
60 52 126
13 21 105
17 20
27 5
13 14

out:

0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

*/