| ||||||||||
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 |
Dijstra算法,大侠的所有数据都能通过,但却不能过oj,很是悲剧,有谁帮看一下吧,有注释#include <iostream> #include <fstream> #include <set> #define MAX_PRICE 10000000 using namespace std; struct commodity { int P,L; int N; }; int minP[105]; //dijstra 算法的距离 int mat[105][105]; //邻接矩阵 int main() { commodity c[105];//所有商品 int M,N; int i,p,l,x,j,No_,P_; //ifstream input; //input.open("data.txt",std::ios::in); while(cin>>M>>N) { memset(mat,0,sizeof(mat)); memset(minP,0,sizeof(minP)); //initialize for( i = 1; i <= N; i++) { for( j = 1; j <= N; j++) { if( i == j) { mat[i][j] = 0; } else mat[i][j] = MAX_PRICE; } } //先输入邻接关系 for( i = 1; i<= N;i++) { cin>>p>>l>>x; minP[i] = p; c[i].P = p; c[i].N = x; c[i].L = l; for( j = 0; j < x; j++) { cin>>No_>>P_; mat[No_][i] = P_; } } //按照地位身份排除一些情况 for( i = 1; i <= N; i++) { for( j = 1; j <= N; j++) { if(mat[i][j] != 0 && mat[i][j] != MAX_PRICE) { if( abs(c[i].L - c[j].L) > M) { mat[i][j] = MAX_PRICE; } } } } //找到原点集合,就是那些没有前驱的点,有一个虚拟节点,这些点到虚拟节点的距离就是他们自己的价格 std::set<int> minset,others; std::set<int>::iterator it,it_j; for( i = 1; i <= N; i++) { int inward = 0; for( j = 1; j <= N; j++) { if(i != j && mat[j][i] != MAX_PRICE) { inward++; } } if(inward == 0) { minset.insert(i); } else others.insert(i); } int dis,minDis; //如果最终的商品也没有前驱,那么只能用金币购买 if(minset.find(1) != minset.end()) { cout<<c[1].P<<endl; } else { //用dijstra算法,找出出虚拟节点到商品1的距离,初始距离不是最大,而是使用每个商品的金币价格 while(1) { for( it = minset.begin(); it != minset.end(); ++it) { for( it_j = others.begin(); it_j !=others.end(); ++it_j) { if(*it != *it_j && mat[*it][*it_j] != MAX_PRICE) minP[*it_j] = min(minP[*it_j],minP[*it] + mat[*it][*it_j]); } } minDis = 1000000000; for( it_j = others.begin(); it_j != others.end() ; ++it_j) { if(minP[*it_j] < minDis) { minDis = minP[*it_j]; it = it_j; } } if(*it == 1) { dis = minDis; break; } minset.insert(*it); others.erase(it); } cout<<dis<<endl; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator