好吧，过了.LCA和一处continue的锅...
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
const int N = 1e5 + 10;
const int M = 3e5 + 10;
int n , m , q , t , cnt;
int father[N] , dep[N];
int bus[N] , Belong[N];
int p[N][25] , minn[N][25];
int ans[N];
bool have[N];
struct Coust {
int val;
bool buy;
}c[N];
struct Edge {
int from;
int to;
int next;
int MaxAu;
}e[M],te[M];
int head[N];
inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
inline void add ( int x , int y , int z ) {
te[++t].from = x;
te[t].to = y;
te[t].MaxAu = z;
te[t].next = head[x];
head[x] = t;
return;
}
inline int min ( int x , int y ) {
return x < y ? x : y;
}
inline void swap ( int &x , int &y ) {
int t = x;
x = y;
y = t;
return;
}
int find ( int x ) {
if ( father[x] != x ) father[x] = find ( father[x] );
return father[x];
}
void Union ( int x , int y ) {
x = find ( x ) , y = find ( y );
father[x] = y;
return;
}
bool Juege ( int x , int y ) {
x = find ( x ) , y = find ( y );
if ( x == y ) return true;
else return false;
}
bool cmp ( Edge x , Edge y ) {
return x.MaxAu > y.MaxAu;
}
void Creat ( int root , int fa ) {
dep[root] = dep[fa] + 1;
for ( int i = head[root] ; i ; i = te[i].next ) {
int j = te[i].to;
if ( j == fa )
continue;
else {
p[j][0] = root;
minn[j][0] = te[i].MaxAu;
Creat ( j , root );
}
}
return;
}
inline int LCA ( int x , int y ) {
int ans = 1e14;
if ( dep[x] > dep[y] )
swap ( x , y );
for ( int i = 24 ; i >= 0 ; i-- )
if ( dep[x] <= dep[y] - ( 1 << i ) ) {
ans = min ( ans , minn[y][i] );
y = p[y][i];
}
if ( x == y )
return ans;
for ( int i = 24 ; i >= 0 ; i-- ) {
if ( p[x][i] == p[y][i] )
continue;
ans = min ( ans , min ( minn[x][i] , minn[y][i] ) );
x = p[x][i];
y = p[y][i];
}
ans = min ( ans , min ( minn[x][0] , minn[y][0] ) );
return ans;
}
signed main ( void ) {
std :: memset ( minn , 0x3f3f3f3f , sizeof ( minn ) );
n = read () , m = read () , q = read ();
for ( int i = 1 ; i <= n ; i++ )
bus[i] = read ();
for ( int i = 1 ; i <= n ; i++ ) {
c[i].val = read ();
if ( c[i].val < 0 ) {
c[i].val = -1 * c[i].val;
c[i].buy = 1;
}
}
for ( int i = 1 ; i <= m ; i++ ) {
int x = read () , y = read () , z = read ();
e[i].from = x;e[i].to = y;e[i].MaxAu = z;
}
for ( int i = 1 ; i <= q ; i++ ) {
int x = read ();
have[x] = 1;
}
for ( int i = 1 ; i <= n ; i++ )
if ( !have[i] )
Belong[i] = ++cnt;
cnt++;
if ( !q )
cnt--;
for ( int i = 1 ; i <= n ; i++ )
if ( have[i] )
Belong[i] = cnt;
// for ( int i = 1 ; i <= n ; i++ )
// std :: cout << Belong[i] << std :: endl;
std :: sort ( e + 1 , e + m + 1 , cmp );
for ( int i = 1 ; i <= cnt ; i++ )
father[i] = i;
int NowNode = 0;
for ( int i = 1 ; i <= m ; i++ ) {
int l = Belong[e[i].from] , r = Belong[e[i].to];
//printf ( "%lld %lld\n" , Belong[e[i].from] , Belong[e[i].to] );
//printf ( "%lld\n" , NowNode );
if ( !Juege ( l , r ) ) {
Union ( l , r );
NowNode++;
add ( l , r , e[i].MaxAu );
add ( r , l , e[i].MaxAu );
}
if ( NowNode == cnt - 1 )
break;
}
// for ( int i = 1 ; i <= t ; i++ )
// printf ( "%lld %lld %lld\n" , te[i].from , te[i].to , te[i].MaxAu );
Creat ( 1 , 0 );
for ( int j = 1 ; j <= 24 ; j++ )
for ( int i = 1 ; i <= cnt ; i++ )
p[i][j] = p[p[i][j - 1]][j - 1];
for ( int j = 1 ; j <= 24 ; j++ )
for ( int i = 1 ; i <= cnt ; i++ )
minn[i][j] = min ( minn[i][j - 1] , minn[p[i][j - 1]][j - 1] );
// for ( int i = 1 ; i <= cnt ; i++ )
// printf ( "Node:%lld Deep:%lld father:%lld FromEdge:%lld\n" , i , dep[i] , p[i][0] , minn[i][0] );
int qwq = 0;
int NowPlace = 0;
int NowMoney = 0;
for ( int i = 1 ; i <= n ; i++ ) {
// using std :: cout;
// using std :: endl;
// cout << i << " " << bus[i] << " " << NowPlace << " " << NowMoney << endl;
if ( Belong[bus[i]] == Belong[NowPlace] ) {
if ( c[bus[i]].buy ) {
qwq++;
if ( NowMoney >= c[bus[i]].val ) {
ans[qwq] = c[bus[i]].val;
NowMoney -= c[bus[i]].val;
}
else {
ans[qwq] = NowMoney;
NowMoney = 0;
}
}
else
NowMoney += c[bus[i]].val;
}
else {
int mins = LCA ( Belong[NowPlace] , Belong[bus[i]] );
NowMoney = min ( NowMoney , mins );
if ( c[bus[i]].buy ) {
qwq++;
if ( NowMoney >= abs ( c[bus[i]].val ) ) {
ans[qwq] = c[bus[i]].val;
NowMoney -= c[bus[i]].val;
}
else {
ans[qwq] = NowMoney;
NowMoney = 0;
}
}
else
NowMoney += c[bus[i]].val;
}
NowPlace = bus[i];
}
for ( int i = 1 ; i <= qwq ; i++ )
printf ( "%lld\n" , ans[i] );
return 0;
}
```
by 兮水XiShui丶 @ 2018-10-16 16:43:28
@[Kirito_Rivaille](/space/show?uid=54047) %%%做紫题的大佬
by 宇智波—鼬 @ 2018-10-16 16:46:01