今天考了一道分层图，本来是一道板题，结果我被误导了，想成了 架设电话线一题，考完写炸了才发现，架设电话线只需要求出第k+1大的长度，只需要满足局部最优，但是飞行线路要使总和最小，只能用分层图，然后我翻了半天标签，找到了这道题。
link
但是当旁边LH看到之后，他告诉我，这是一道DP。
结果我没看出来。。。
分层图倒是很简单。
Sulotion
step1 首先，他可以在图上到处走动，所以很自然地可以建一张图，所有的边权都是0。 然后这道题只与水晶球的价格有关，所以我们把点权搬到边权上面。 step2 因为他只进行一次买卖，所以有下面两种情况： 假设从
u
u
u到
v
v
v，水晶球在
u
u
u的价格为
w
w
w. 1.买. 建第二层图，连接第一层图 -> 在
u
u
u和
v
v
v之间建一条边边权为
−
w
-w
−w。 2.卖. 建第三层图，连接第二层图 -> 在
u
u
u和
v
v
v之间建一条边边权为
w
w
w。 step3 我们在最后有两种方法走向终点： 不买卖直接走向终点 直接在第一层图的n号节点建立边权为0的有向边接入一个“大终点” 买卖一次后走向终点 在第三层图的n号节点建立边权为0的有向边接入“大终点”
至此，这道题就只需要求一个最长路即可。
Code
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std
;
const int MAXN
= 100005 * 3 + 1;
int n
, m
, a
[MAXN
];
bool vis
[MAXN
];
int dis
[MAXN
];
queue
<int> q
;
void read(int& x
) {
x
= 0;
int f
= 1;
char c
= getchar();
while (c
> '9' || c
< '0') {
if (c
== '-') f
= -f
;
c
= getchar();
}
while (c
<= '9' && c
>= '0') {
x
= x
* 10 + c
- '0';
c
= getchar();
}
x
*= f
;
}
struct edge
{
int v
, w
;
edge(){}
edge(int V
, int W
) {
v
= V
;
w
= W
;
}
};
vector
<edge
> G
[MAXN
];
void AddEdge(int u
, int v
, int w
) {
G
[u
+ n
* 0].push_back(edge(v
+ n
* 0, 0));
G
[u
+ n
* 1].push_back(edge(v
+ n
* 1, 0));
G
[u
+ n
* 2].push_back(edge(v
+ n
* 2, 0));
G
[u
+ n
* 0].push_back(edge(v
+ n
* 1, -w
));
G
[u
+ n
* 1].push_back(edge(v
+ n
* 2, w
));
}
void Spfa() {
memset(vis
, 0, sizeof(vis
));
memset(dis
, 0xcf, sizeof(dis
));
dis
[1] = 0;
vis
[1] = 1;
q
.push(1);
while (q
.size()) {
int u
= q
.front();
q
.pop();
vis
[u
] = 0;
for (int i
= 0; i
< G
[u
].size(); i
++) {
int v
= G
[u
][i
].v
, w
= G
[u
][i
].w
;
if (dis
[v
] < dis
[u
] + w
) {
dis
[v
] = dis
[u
] + w
;
if (vis
[v
] == 0) {
vis
[v
] = 1;
q
.push(v
);
}
}
}
}
printf
("%d\n", dis
[n
]);
}
int main() {
read(n
);
read(m
);
for (int i
= 1; i
<= n
; i
++) {
read(a
[i
]);
}
for (int i
= 1, u
, v
, opt
; i
<= m
; i
++) {
read(u
), read(v
), read(opt
);
AddEdge(u
, v
, a
[u
]);
if (opt
== 2) {
AddEdge(v
, u
, a
[v
]);
}
}
G
[n
].push_back(edge(n
* 3 + 1, 0));
G
[n
* 3].push_back(edge(n
* 3 + 1, 0));
n
*= 3;
n
++;
Spfa();
return 0;
}
