。。。 总是没思路 真要命
注意两点之间可能有多条权值不同的路径，不过只要在输入时取最小值就好了。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<iomanip> 10 #include<climits> 11 #include<string.h> 12 #include<cmath> 13 #include<stdlib.h> 14 #include<vector> 15 #include<set> 16 #define INF 1e7 17 #define MAXN 100010 18 #define maxn 50 19 #define maxm 1000 20 #define Mod 1000007 21 using namespace std; 22 typedef long long LL; 23 24 25 int T; 26 int s, n, m; 27 int a, b, c; 28 int v[110]; 29 int G[110][110]; 30 int dist[1000010]; 31 int vis[110]; 32 int dp[1000010]; 33 34 void Dijkstra() 35 { 36 for (int i = 0; i <= n; ++i) 37 dist[i] = G[0][i],vis[i] = 0; 38 int pos, min; 39 vis[0] = 1; 40 dist[0] = 0; 41 for (int i = 1; i <= n; ++i) { 42 min = INF; 43 for (int j = 1; j <= n; ++j) { 44 if (!vis[j] && min > dist[j]) { 45 pos = j; 46 min = dist[j]; 47 } 48 } 49 vis[pos] = 1; 50 for (int j = 1; j <= n; ++j) { 51 if (!vis[j] && dist[j] > dist[pos] + G[pos][j]) 52 dist[j] = dist[pos] + G[pos][j]; 53 } 54 } 55 } 56 57 void bag01() 58 { 59 for (int i = 1; i <= n; ++i) 60 for (int j = s; j >= dist[i]; --j) 61 dp[j] = max(dp[j - dist[i]] + v[i],dp[j]); 62 } 63 64 void run() 65 { 66 scanf("%d%d%d", &s, &n, &m); 67 memset(v,0,sizeof(v)); 68 memset(dp,0,sizeof(dp)); 69 for (int i = 0; i <= n; ++i) 70 for (int j = 0; j <= n; ++j) 71 G[i][j] = INF; 72 for (int i = 0; i < m; ++i) { 73 scanf("%d%d%d", &a, &b, &c); 74 if (c < G[a][b]) 75 G[a][b] = G[b][a] = c; 76 } 77 for (int i = 1; i <= n; ++i) 78 scanf("%d",&v[i]); 79 Dijkstra(); 80 bag01(); 81 printf("%d ",dp[s]); 82 } 83 int main() 84 { 85 scanf("%d", &T); 86 while (T--) 87 run(); 88 return 0; 89 }