#include<iostream> #include<stdio.h> #define MAXN 105 #define inf 10000000 using namespace std; struct dest { int next; int len; }; struct node { int money; int stat; int dest_num; dest coll[MAXN]; }; int give_ans(int rang_b,int rang_e); void Dijkstra(int m,int s); node man[MAXN]; int _m[MAXN][MAXN]; int dij[MAXN]; bool last[MAXN]; int n; int main() { //freopen("acm.acm","r",stdin); int m; int i; int j; int tem; int min; int rang_begin; int rang_end; cin>>m>>n; memset(last,false,sizeof(last)); for(i = 0; i < n; ++ i) { cin>>man[i].money; cin>>man[i].stat; cin>>man[i].dest_num; if(man[i].dest_num == 0) last[i] = true; for(j = 0; j < man[i].dest_num; ++ j) { cin>>man[i].coll[j].next; -- man[i].coll[j].next; cin>>man[i].coll[j].len; } } min = inf; for(i = 0; i <= m; ++ i) { rang_begin = man[0].stat; rang_end = rang_begin; rang_begin -= (m - i); rang_end += i; // cout<<rang_begin<<" "<<rang_end<<endl; tem = give_ans(rang_begin,rang_end); // cout<<tem<<" 8888888888888888"<<endl; if(tem < min) min = tem; //cout<<min<<endl; } if(min != inf) cout<<min<<endl; else cout<<man[0].money<<endl; } int give_ans(int rang_b,int rang_e) { int i; int j; int _min; for(i = 0; i < n; ++ i) { for(j = 0; j < n; ++ j) { _m[i][j] = inf; } } for(i = 0; i < n; ++ i) ///////////////敏感地区 { if(man[i].stat >= rang_b && man[i].stat <= rang_e) for(j = 0; j < man[i].dest_num; ++ j) { if(man[man[i].coll[j].next].stat >= rang_b && man[man[i].coll[j].next].stat <= rang_e) { _m[i][man[i].coll[j].next] = man[i].coll[j].len; // if(man[man[i].coll[j].next].dest_num == 0) // _m[i][man[i].coll[j].next] += man[man[i].coll[j].next].money; } } } // cout<<"b dij"<<endl; // for(i = 0; i < n; ++ i) // { // cout<<i<<" "; // for(j = 0; j < n; ++ j) // { // if(_m[i][j] != inf) // cout<<j<<" "; // } // cout<<endl; // } Dijkstra(n,0); // cout<<"DIJ"<<endl; _min = inf; for(i = 1; i < n; ++ i) { if(dij[i] != -1 && dij[i] < _min) { _min = dij[i]; } } return _min; } void Dijkstra(int m,int s) { int i; int j; int min; int * mark = new int[m]; memset(mark,0,m*sizeof(int)); memset(dij,-1,sizeof(dij)); dij[s] = 0; mark[s] = 1; int x; int k; min = -1; for(i = 0; i < m; ++ i) { if(_m[s][i] != inf) dij[i] = _m[s][i]; } for(k = 0; k < m; k++) { min = -1; for(j = 0; j < m; j++) { if(mark[j] == 0 && dij[j] > 0) { if(dij[j] < min || min < 0) { min = dij[j]; x = j; } } } //cout<<"7777777777777"<<endl; if(min == -1) break; mark[x] = 1; for(i = 0; i < m; ++ i) { if(mark[i] == 0 && _m[x][i] != inf) { if(dij[i] < 0 || dij[x] + _m[x][i] < dij[i]) { dij[i] = dij[x] + _m[x][i]; } } } } for(i = 0; i < m; ++ i) { if(dij[i] != -1) { dij[i] += man[i].money; // cout<<dij[i]<<" "; } } // cout<<endl; delete []mark; }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com