程序设计天梯赛L3-22 (小丑竟是我自己)

题目 题意: 我一开始以为题意有问题，后来看了题解看了半天才看明白题意，小丑竟是我自己。n个点，m条线路，每条线路给出若干条边，费用变化为每走k便加1。给定T个询问，以T为起点可以到达多少个可以拍照的点。可以在费用相同的最远距离的点、线路端点处进行拍照。而且我们可以通过在多条线路中都出现的点在这些线路中切换。在起点处也能拍照。解释不太清楚，反正挺离谱。 思路: floyd处理最短路，Dij应该也行。然后dfs求出所有满足条件的点。而且这个输入还卡了我一个段错误，换成while getchar就行了，属于是不明白。 时间复杂度: O(n^3 + n) 代码:

#include
using namespace std;
const int N = 1002;
const int INF = 0x3f3f3f3f;
int n,m,k,T;
bool line[N];
int a[N][N];
vector va[N]; //点i可以到的费用相同的最远的点和端点
map mp; //费用i对应的最远的点
bool vis[N];
void floyd()
{
	for(int k=1;k>m>>k;
	for(int i=1;i>z>>y;
            a[x][y] = min(a[x][y],z);
            a[y][x] = min(a[y][x],z);
            x = y;
        }
        line[x] = 1;
	}
	floyd();
	for(int i=1;i>x;
		memset(vis,false,sizeof(vis));
        vis[x] = 1;
        dfs(x);
		bool ok = true;
		for(int i=1;i