这道题删完边后是一棵树，那么一定和最小生成树有关啦。
考虑最后的生成树，无论从哪一个点出发，每一条边都会访问两次，而且在看一看样例，会发现走第w条边(u, v)的代价是L[w] * 2 + c[u] + c[v],所以说把每一条边的边权改为这个，然后跑裸的最小生成树就行了。然后答案还要加上出发的点的权值，那自然要加权值最小的点。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<stack> 8 #include<queue> 9 #include<vector> 10 #include<cctype> 11 using namespace std; 12 #define space putchar(' ') 13 #define enter puts("") 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 1e4 + 5; 20 const int max_size = 1e5 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = (ans << 3) + (ans << 1) + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) putchar('-'), x = -x; 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 37 int n, m, a[maxn]; 38 struct Node 39 { 40 int x, y, cost; 41 bool operator < (const Node& other)const 42 { 43 return cost < other.cost; 44 } 45 }t[max_size]; 46 47 int p[maxn]; 48 void init() 49 { 50 for(int i = 1; i <= n; ++i) p[i] = i; 51 } 52 int Find(int x) 53 { 54 return x == p[x] ? x : p[x] = Find(p[x]); 55 } 56 57 int ans = 0, cnt = 0, Min = INF; 58 59 int main() 60 { 61 n = read(); m = read(); 62 for(int i = 1; i <= n; ++i) a[i] = read(), Min = min(Min, a[i]); 63 for(int i = 1; i <= m; ++i) 64 { 65 t[i].x = read(); t[i].y = read(); t[i].cost = read(); 66 t[i].cost = (t[i].cost << 1) + a[t[i].x] + a[t[i].y]; 67 } 68 sort(t + 1, t + m + 1); 69 init(); 70 for(int i = 1; i <= m; ++i) 71 { 72 int px = Find(t[i].x), py = Find(t[i].y); 73 if(px != py) 74 { 75 p[px] = py; 76 ans += t[i].cost; cnt++; 77 if(cnt == n - 1) break; 78 } 79 } 80 write(ans + Min); enter; 81 return 0; 82 }