学步园

这题，初看没什么思路，下午看的时候挺困的，去床上躺了会儿，想通了，水题呀~~

给你几条路线，从一条路线到另一条路线需要重新买票，给出K个人的位置，每个人都需要到达同一个点去，每个人有钱，有的还有月票（月票的话乘车不要钱~）问你到哪个点，总的花费最小，输出位置和最小花费。如果不能到达，输出0。

建图，每条路上任意两点的权为1，然后用floyd找从一个点到另一个点的最短路。然后枚举到达地点即可。

处理月票和是否连通需要注意下。

#include <queue><br /> #include <stack><br /> #include <math.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <limits.h><br /> #include <string.h><br /> #include <algorithm></p> <p>using namespace std;</p> <p>const int MAX = 110;<br /> typedef struct FFF{<br /> int money,pos,tik;<br /> }FFF;<br /> FFF f[110];<br /> int map[MAX][MAX];<br /> int n,fnum,tpos;<br /> int road[MAX],mincost;<br /> void Floyd()<br /> {<br /> for(int i=1; i<=n; i++)<br /> for(int k=1; k<=n; k++)<br /> for(int j=1; j<=n; j++)<br /> if( map[k][i] != INT_MAX && map[i][j] != INT_MAX<br /> && map[k][j] > map[k][i] + map[i][j] )<br /> map[k][j] = map[k][i] + map[i][j];<br /> }</p> <p>int compute(int x)<br /> {<br /> int cost = 0;<br /> for(int k=0; k<fnum; k++)<br /> {<br /> if( map[x][f[k].pos] == INT_MAX )<br /> return -1;<br /> if( !f[k].tik && map[x][f[k].pos] > f[k].money )<br /> return -1;<br /> if( !f[k].tik )<br /> cost += map[x][f[k].pos];<br /> }<br /> return cost;<br /> }</p> <p>int solve()<br /> {<br /> for(int i=1; i<=n; i++)<br /> {<br /> int ans = compute(i);<br /> if( ans != -1 && ans < mincost )<br /> {<br /> mincost = ans;<br /> tpos = i;<br /> }<br /> }<br /> return mincost;<br /> }</p> <p>int main()<br /> {<br /> int m,num;<br /> scanf("%d %d",&n,&m);<br /> for(int i=1; i<=n; i++)<br /> {<br /> for(int k=1; k<=n; k++)<br /> map[i][k] = INT_MAX;<br /> map[i][i] = 0;<br /> }<br /> while( m-- )<br /> {<br /> scanf("%d",&num);<br /> for(int i=0; i<num; i++)<br /> scanf("%d",&road[i]);<br /> for(int i=0; i<num; i++)<br /> for(int k=i+1; k<num; k++)<br /> map[road[i]][road[k]] = map[road[k]][road[i]] = 4;<br /> }</p> <p> scanf("%d",&fnum);<br /> for(int i=0; i<fnum; i++)<br /> scanf("%d%d%d",&f[i].money,&f[i].pos,&f[i].tik);</p> <p> Floyd();</p> <p> mincost = INT_MAX;<br /> int ans = solve();<br /> if( ans == INT_MAX )<br /> printf("0/n");<br /> else<br /> printf("%d %d/n",tpos,ans);</p> <p>return 0;<br /> }