原题:https://pintia.cn/problem-sets/994805342720868352/problems/994805489282433024
第一次的失败代码:
1 #include<iostream> 2 #include<vector> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 using namespace std; 7 8 const int maxLen = 500 + 10; 9 int send, back, res_step, bike[maxLen], road[maxLen][maxLen]; 10 int Cmax, N, Sp, M, x, y, t, half, flag; 11 bool vis[maxLen][maxLen]; 12 vector<int> path, temp_path; 13 14 void dfs(int s,int sum,int step) { 15 if (Sp == s) { 16 if (step > res_step) return; 17 int send1 = sum >= half - bike[Sp] ? 0 : half - bike[Sp] - sum; 18 int back1 = send1 > 0 ? 0 : sum - (half - bike[Sp]); 19 if (step < res_step) { 20 send = send1; 21 back = back1; 22 res_step = step; 23 path = temp_path; 24 } 25 else if (step == res_step) { 26 if (send1 > send || (send1 == send && back1 > back)) return; 27 send = send1; 28 back = back1; 29 path = temp_path; 30 } 31 return; 32 } 33 for (int i = 1;i<=N;i++) { 34 if (vis[s][i] == false && road[s][i] != -1) { 35 vis[s][i] = vis[i][s] = true; 36 temp_path.push_back(i); 37 int ds = bike[i] > half ? bike[i] - half : 0; 38 dfs(i, sum + ds, step + road[s][i]); 39 temp_path.pop_back(); 40 vis[s][i] = vis[i][s] = false; 41 } 42 } 43 } 44 45 int main() 46 { 47 while (cin >> Cmax >> N >> Sp >> M) { 48 memset(bike, 0, sizeof(bike)); 49 memset(road, -1, sizeof(road)); 50 memset(vis, 0, sizeof(vis)); 51 for (int i = 1; i <= N; i++) scanf("%d", &bike[i]); 52 for (int i = 0; i < M; i++) { 53 scanf("%d %d %d", &x, &y, &t); 54 road[x][y] = road[y][x] = t; 55 } 56 half = Cmax / 2; vis[0][0] = true; 57 send = res_step = back = 0x7fffffff; 58 temp_path.push_back(0); 59 flag = bike[Sp] >= half ? 1 : 0; 60 dfs(0, 0, 0); 61 cout << send << " "; 62 for (int i = 0; i < path.size(); i++) { 63 printf("%d", path[i]); 64 if (i != path.size() - 1) printf("->"); 65 else printf(" "); 66 } 67 if (flag) printf("%d\n", bike[Sp] - half); 68 else printf("%d\n", back); 69 } 70 return 0; 71 }
p