【CSU-1321】解题报告（最短路，dij）

原始题目

1321: CX and girls

  • Time Limit: 1 Sec
  • Memory Limit: 128 Mb
  • Submitted: 597
  • Solved: 181

Description

CX是要赶去上课，为了不迟到必须要以最短的路径到达教室，同时CX希望经过的路上能看到的学妹越多越好。 现在把地图抽象成一个无向图，CX从\(1\)点出发，教室在\(N\)号点，告诉每个点上学妹的数量，每条边的长度。

请你求出CX以最短路径赶到教室最多能看到多少学妹。

Input

多组输入数据(最多20组)，输入到文件结束。

每组数据第一行两个正整数\(N,M\)其中\(N\)代表点的个数\(( 2 ≤ N ≤ 1000)\)，\(M\)代表边的个数\((1 ≤ M ≤ 10000)\)。

接下来一行\(N\)个数，代表着\(1 \cdots N\)每个点上学妹的个数，\((0 ≤ N_i \le 50)\)。 接下来\(M\)行，每行三个数\(A,B,C (1 \le A , B \le N , 0 < C \le 100 )\) 代表\(A,B\)两点间有边，长度为\(C\)。(可能存在重边)

Output

输出CX以最短距离从\(1\)到\(n\)的情况下能看到的最多学妹数量，若从点\(1\)无法到达点\(N\)输出\(-1\)。

Sample Input

4 4
1 2 3 4
1 2 1
1 3 1   
2 4 2
3 4 2

Sample Output

8

Author

CSU_ZZY

Source

CSU Monthly 2013 Oct.

题目大意

如题

解题思路

最短路加上对结点值的判断

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <bits/stdc++.h> 
using namespace std;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define np next_permutation
#define ms(x,a) memset((x),(a),sizeof(x))
//优先队列迪杰斯特拉 
const int maxn=1e5+5;
struct Edge{
	int u,v,w;
	Edge(int _u,int _v,int _w):u(_u),v(_v),w(_w){
	};
};
vector <Edge> edges[maxn];

int dis[maxn],meizi[maxn],mei[maxn];
bool vis[maxn];
int n,m,uu,vv,ww;

void init(int n){ //n个结点的边集都清空 
	rep(i,0,maxn){
		edges[i].clear();
	}
}

void addEdge(int u,int v,int w){
	edges[u].pb(Edge(u,v,w));
}

struct Node{
	int Id,W;
	Node(int _Id,int _W):Id(_Id),W(_W){
	};
	bool operator < (const Node &b) const {
		return W>b.W;
//		else return Id<b.Id;
	}
};

void Dijkstra(int s){
	ms(vis,0);
	ms(meizi,0);
	ms(dis,INF);
	priority_queue <Node> q;
	q.push(Node(s,0)) ;
	dis[s]=0;meizi[s]=mei[s];
	while(!q.empty()){
		Node now=q.top();
		q.pop();
		int index=now.Id;
		if(vis[index]) continue;
//		if(index==end) return;
		vis[index]=1;
		rep(i,0,edges[index].size()){
			Edge temp=edges[index][i];
			if(dis[temp.v]>dis[index]+temp.w){
				dis[temp.v]=dis[index]+temp.w;
				meizi[temp.v]=meizi[index]+mei[temp.v];
				q.push(Node(temp.v,dis[temp.v]));
			}
			else if(dis[temp.v]==dis[index]+temp.w){
				if(meizi[temp.v]<meizi[index]+mei[temp.v]){
					meizi[temp.v]=meizi[index]+mei[temp.v];
					q.push(Node(temp.v,dis[temp.v]));
				}
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);

	while(cin>>n>>m){
		init(n);
		rep(i,1,n+1){
			cin>>mei[i];
		}
		rep(i,1,m+1){
			cin>>uu>>vv>>ww;
			addEdge(uu,vv,ww);
			addEdge(vv,uu,ww);
		} 
		Dijkstra(1);
		if(dis[n]>100000000) cout<<"-1"<<endl;
		else cout<<meizi[n]<<endl;
	} 
}


收获与反思

  • 模板开始错了，少了return，WA了一晚上。