将线路和车站都抽象为结点，bfs计算最短路，注意有月票的人携带的钱看作无穷多
1 #include <iostream>
2 using namespace std;
3 const int OO=2000000;
4 int n,m,f;
5 int link[300][300];
6 int dis[300][300];
7 int money[200],start[200];
8 int reach[200][300];
9 bool month[200];
10 int q[300][2],st,en;
11 bool v[300];
12 void bfs(int s){
13 int x=start[s];
14 for (int i=1;i<=m+n;++i) v[i]=false;
15 q[1][0]=x;
16 q[1][1]=0;
17 st=0; en=1;
18 v[x]=true;
19 reach[s][x]=0;
20 while(st<en){
21 ++st;
22 if (q[st][1]>money[s]) continue;
23 int nx=q[st][0];
24 for (int i=1;i<=link[nx][0];++i) if (!v[link[nx][i]]){
25 ++en;
26 q[en][0]=link[nx][i];
27 q[en][1]=q[st][1]+2;
28 if (q[en][1]>money[s]) break;
29 reach[s][link[nx][i]]=q[en][1];
30 v[link[nx][i]]=true;
31 }
32 }
33 }
34 int main(){
35 scanf("%d %d",&n,&m);
36 for (int i=1;i<=m;++i){
37 int l;
38 scanf("%d",&l);
39 for (int j=1;j<=l;++j){
40 int x;
41 scanf("%d",&x);
42 link[n+i][++link[n+i][0]]=x;
43 link[x][++link[x][0]]=n+i;
44 }
45 }
46 scanf("%d",&f);
47 for (int i=1;i<=f;++i){
48 int a,b,c;
49 scanf("%d %d %d",&a,&b,&c);
50 money[i]=a;
51 start[i]=b;
52 month[i]=c;
53 if (c==1) money[i]=OO;
54 }
55 for (int i=1;i<=f;++i)
56 for (int j=1;j<=m+n;++j) reach[i][j]=OO;
57 for (int i=1;i<=f;++i) bfs(i);
58
59 int ans=OO,apos=0;
60 for (int i=1;i<=n;++i){
61 int sum=0;
62 for (int j=1;j<=f;++j){
63 if (month[j]==0)sum+=reach[j][i];
64 else if (reach[j][i]>=OO){
65 sum=OO;
66 break;
67 }
68 }
69 if (sum<ans){
70 ans=sum;
71 apos=i;
72 }
73 }
74 if (apos==0) cout<<0;
75 else printf("%d %d",apos,ans);
76 }
77
posted on 2008-11-09 17:27
Joseph 阅读(270)
评论(0) 编辑 收藏 引用