【t087】公共汽车
Time Limit: 1 second Memory Limit: 128 MB
【问题描述】
路人丁成为了一名新公交车司机，每个司机都有一张牌子，牌子的正面写了拥有这个牌子的司机开的线路号，另外一面随便写了一 个号码。但是路人丁的牌子两面写的都不是自己开的线路号。所以他决定跟其他人换，当然，所有的司机都只有当路人丁手里 的牌子上的某面写了自己的线路号时才愿意跟他换。所以路人丁想知道自己至少要换几次牌子才能换到一张写有自己线路号的 牌子。 【输入格式】
第一行包括一个整数K（K≤1000），表示车的数量（新车除外）。这些车的编号依次从1到K。接下来的K行，每行包括此车对应的线路号和牌子另一面的号码（长整范围的数字）。 最后一行是安排路人丁开的公交车线路号以及给他的牌子上的号码。
【输出格式】
首行是最少交换的次数M，接下来的M行顺序输出要交换牌子的车的编号。如果没有方案，则输出 IMPOSSIBLE。
Sample Input
4 8 5 5 4 7 4 1 5 4 1 8
Sample Output
2 4 2
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t087
【题意】
【题解】 牌子的另外一面对应的交通线; 看看是哪个公交的交通线; 然后用一条边由前者指向后者; 表示可以从前者换到后者; 肯定没有必要连成一个环啦; 想象一下就是一个牌子一直和另外一个牌子换。 跑个最短路写个路径输出就好 (建图的话一定要按照代码的方式建图) 不然方案和答案会不一样。 (可能会不一样) (算是贪心吧? 【完整代码】
#include <cstdio> #include <algorithm> #include <vector> #include <cmath> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define pb push_back #define fi first #define se second #define rei(x) scanf("%d",&x) #define rel(x) scanf("%lld",&x) typedef pair<int, int> pii; typedef pair<LL, LL> pll; const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 }; const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 }; const double pi = acos(-1.0); const int N = 1100; int n,a1,a2; int idx[N],ano[N]; int dis[N],PRe[N],dl[N],h,t; int zh[N]; vector <int> G[N]; void output_ans(int now) { if (pre[now] == 0) return; output_ans(pre[now]); printf("%d\n", dl[now]); } int main() { //freopen("F:\\rush.txt", "r", stdin); rei(n); rep1(i, 1, n) rei(idx[i]), rei(ano[i]); rei(idx[n + 1]), rei(a1), rei(a2); if (a1 == idx[n + 1] || a2 == idx[n + 1]) { puts("0"); return 0; } rep1(i, 1, n) { rep1(j, 1, n) { if (ano[i] == idx[j]) G[i].push_back(j); } if (a1 == idx[i] || a2==idx[i]) G[n + 1].push_back(i); } memset(dis, 255, sizeof dis); dis[n + 1] = 0; h = 1, t = 1; dl[1] = n + 1; while (h <= t) { int x = dl[h++]; int len = G[x].size(); rep1(i, 0, len - 1) { int y = G[x][i]; if (dis[y] == -1) { dis[y] = dis[x] + 1; dl[++t] = y; pre[t] = h - 1; if (ano[y] == idx[n + 1]) { printf("%d\n", dis[y]); output_ans(t); return 0; } } } } puts("IMPOSSIBLE"); return 0; }