Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我的程序,不知道错哪里了,老wa#include <iostream> using namespace std; const int MAX = 999999; int **city; int n, k; int a, b, d; int i, j; int num; int m; int *visit; bool *arrived; int best = MAX; void search(int v, int sum, int number) { if(number == 0) { if(best > sum) { best = sum; } return; } if(sum > best) { return; } int i; for(i = 1; i <= num; i++) { int temp = visit[i]; if(!arrived[temp]) { arrived[temp] = true; search(temp, sum + city[v][visit[i]], number - 1); arrived[temp] = false; } } } int main() { while(cin>>n>>k) { city = new int*[n + 1]; for(i = 0; i <= n; i++) { city[i] = new int[n + 1]; } for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { if(i == j) { city[i][j] = 0; } else { city[i][j] = MAX; } } } arrived = new bool[n + 1]; memset(arrived, false, sizeof(arrived)); for(i = 0; i < n - 1; i++) { cin>>a>>b>>d; city[a][b] = city[b][a] = d; } cin>>num; visit = new int[num + 1]; for(i = 1; i <= num; i++) { cin>>visit[i]; } int u, v, w; for(u = 1; u <= n; u++) { for(v = 1; v <= n; v++) { for(w = 1; w <= n; w++) { if(city[v][u] + city[u][w] < city[v][w]) { city[v][w] = city[v][u] + city[u][w]; } } } } arrived[k] = true; search(k, 0, num); cout<<best<<endl; delete [] visit; delete [] arrived; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator