【杭电多校第四场 B题】最短路图+缩点dp

题目链接

题目描述：

题意：

题意就是给你一个有向图，每条边有两个权值，问第一个权值的最短路是多少，而且在第一个权值最小的情况下第二个权值之和的最大值是多少

分析：

很容易想到的就是跑一个最短路然后建一个最短路图再跑一个最长路，因为可能有环，所以跑一个spfa就直接出来，好多人都是这么想的，但是这样想是不对的，因为有环的话跑最长路一定是有问题的，所以说咱们可以用tarjan算法把这个有向图给缩成DAG，然后dp就行，dp[i]代表从1号点所在的连通块到i号联通块的第二个权值之和的最大值，下面请看代码：

#include
#define int long long
using namespace std;
const int N = 200010,M = 300010;
int h[N],e[M+M],w[M+M],p[M+M],ne[M+M],idx;
int h1[N],e1[M+M],w1[M+M],p1[M+M],ne1[M+M],idx1;
inline void add(int a,int b,int c,int d) {
	e[idx] = b;
	w[idx] = c;
	p[idx] = d;
	ne[idx] = h[a];
	h[a] = idx++;
}
inline void add1(int a,int b,int c,int d) {
	e1[idx1] = b;
	w1[idx1] = c;
	p1[idx1] = d;
	ne1[idx1] = h1[a];
	h1[a] = idx1++;
}
inline int read() {
	int f=1,x=0;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return f*x;
}
int n,m;
int dfn[N],low[N],bel[N],tt,cnt,ww[N];
bool ins[N];
stack<int> stk;
vector<vector<int> > scc;
bool st[N];
int dis[N];
int dijkstra(int start,int end) {
	for(int i=1; i<=n; i++) dis[i] = 0x3f3f3f3f3f3f3f3f,st[i] = false;
	dis[start] = 0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	q.push(make_pair(0,start));
	while(q.size()) {
		int t = q.top().second;
		q.pop();
		if(st[t]) continue;
		st[t] = true;
		for(int i=h[t]; i!=-1; i=ne[i]) {
			int j = e[i];
			if(dis[j] > dis[t] + w[i]) {
				dis[j] = dis[t] + w[i];
				q.push(make_pair(dis[j],j));
			}
		}
	}
}
void dfs(int u) {
	dfn[u] = low[u] = ++tt;
	stk.push(u);
	ins[u] = true;
	for(int i=h1[u]; i!=-1; i=ne1[i]) {
		int v = e1[i];
		if(!dfn[v]) dfs(v);
		if(ins[v]) low[u] = min(low[u],low[v]);
	}
	if(low[u] == dfn[u]) {
		++cnt;
		while(true) {
			int v = stk.top();
			stk.pop();
			ins[v] = false;
			bel[v] = cnt;
			if(u == v) break;
		}
	}
}
int deg[N],f[N];
void topo(){
	queue<int> q;
	for(int i=1;i<=cnt;i++) if(!deg[i]) q.push(i);
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i]){
			int j = e[i];
			deg[j]--;
			f[j] = max(f[j],f[t]+p[i]);
			if(!deg[j]) q.push(j);
		}
	}
}
void solve() {
	n = read(),m = read();
	idx1 = cnt = idx = tt = 0;
	for(int i=1; i<=n; i++) h[i] = h1[i] = -1,ins[i] = f[i] = ww[i] = dfn[i] = low[i] = bel[i] = deg[i] = 0;
	while(!stk.empty()) stk.pop();
	while(m--) {
		int u = read(),v = read(),e = read(),p = read();
		add(u,v,e,p);
	}
	dijkstra(1,n);
	printf("%lld ",dis[n]);
	for(int i=1;i<=n;i++){
		for(int k=h[i];k!=-1;k=ne[k]){
			int j = e[k];
			if(dis[j] == dis[i] + w[k]) add1(i,j,w[k],p[k]);
		}
	}
	for(int i=1;i<=n;i++) h[i] = -1;idx = 0;
	for(int i=1; i<=n; i++) if(!dfn[i]) dfs(i);
	for(int i=1; i<=n; i++) {
		for(int k=h1[i]; k!=-1; k=ne1[k]) {
			int j = e1[k];
			if(bel[i] != bel[j]) add(bel[i],bel[j],w1[k],p1[k]),deg[bel[j]]++;
		}
	}
	topo();
	printf("%lld\n",f[bel[n]]);
}
signed main() {
	int _=read();
	while(_--) solve();
	return 0;
}
/*
2
3 3
1 2 1 1
2 3 1 1
1 3 2 0
*/
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131