首页 > 代码库 > 派对选址
派对选址
派对选址
(party.pas/c/cpp)
【题目描述】
在2022年，scu_acmers决定举行一个聚会，并且大多数老 scu_acmers队员已经收到了邀请函，包
括队员 onmylove,tanlinghang和zsasuke(scu_isap队的老队员)。
从 scu毕业已经 10年了，现在他们住在不同的城市。他们都非常傲慢，都认为在所有 scu_acmers
队员中，自己才是最擅长跑步的人。为了证明这一点，他们都决定花上几天时间跑向目的地(聚会所举
办的城市)，并且为了节省体力，他们每个人都会选择最短的路线前往(可能存在多条最短路线，在这种
情况下，他们会随机选择其中的一条)。但是这会导致一系列问题：他们会偶然停下来休息，并且他们
一旦在同一条路上相遇，他们会停止前进，开始争吵谁才是最擅长跑步的人，彻底错过聚会。
Scu 的领导都是考虑周到的人，他们不想让任何一个人错过聚会，因此他们想要选择一个合适的聚
会城市，使得 scu_isap的队员们不会在中途相遇。但是他们都很忙，所以这个任务就交给你了。
【输入文件】
第一行两个正整数 N 和M，表示城市个数和道路条数(onmylove 住在城市 1，tanlinghang 住在城市 2，
zsasuke 住在城市 3)，接下来 M行，每行包含三个正整数a,b,c(1≤a,b≤N,1≤c≤10,b≠a，并且任意
两个城市之间至多只有一条道路直接相连)，表示从a到b 要花费 c天，从b到 a要花费 c天。
【输出文件】
如果不存在这样的城市，输出仅一行”impossible”(不含引号)，否则，第一行输出一个数 P，表示有
P 个城市满足要求，接下来一行，P个用空格隔开的数，表示满足条件的城市编号(升序输出)。
【样例输入】
5 5
1 5 2
4 5 2
5 2 3
2 4 5
3 4 1
【样例输出】
1
5
【样例解释】
我们不能选择 4 号城市。假如我们选择 4 号城市，那么，onmylove 的路线是1-5-4；tanlinghang 的是
2-5-4或2-4；如果tanlinghang选择2-5-4，他将与onmylove在5和4之间的道路上相遇，然后争吵。
【数据规模】
对于10%的数据： 3≤N≤5；1≤M≤10；
对于100%的数据：3≤N≤3000；1≤M≤200000；
派对选址
题目看起来很难的样子，真心不会做。。。
但是，题目中有个突破口——某个人有多条路径可走，而且不能和别人的最短路径有交集——看似使题目变得很难，实际上，要是有交集的话，那么从交点延伸过去的，以这条路为中间路径的某两点之间的最短路上的点（在交点之后）肯定不可行，例子见下——
假设a在1，b在2，c在3。
b和c在4的时候就有了交集，说明在6，7，8，9，10，5，1这几个点是不可以设置Party的。
那么剩下了2，3，4进行判断——
2：a与c会提前相交于4，所以不行；
3：a与b会提前相交于4，所以不行；
4：可行。
（讲的很辣鸡，不懂没关系）
实际上，我们可以先把从1，2，3到每个点的最短路刷出来。
那么，我们肯定要判断每一个点是否可行。
比如我们判断6是否可行——
我们发现，不管点2，点3是否有其他分支，他们总是可能聚集到点4，那么点6自然而然也就不行了。
其实，每当枚举一个点i时，与他所有相邻的点，比如j，如果同时有两个人（a，b，c中的）dis[i]==dis[j]+f[j][i]，说明什么？这两个人都有可能经过j--i这条路，那么不就不可以了？（话说前面我在干什么！！！）归根到底，某一个点是否能举办Party，不是看这个点，而是看与它相邻的点和对应的边的情况（因为如果两个人有交点，交点却就是终点，那也是可以的啊）。好了不说了，不然要祸害苍灵了。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=3005,maxe=400005; 6 int n,m,w[maxe],nxt[maxe],son[maxe],lnk[maxn]; 7 int dis[4][maxn],q[maxn]; 8 int tot=0,h,t,INF; 9 bool vis[maxn]; 10 int ans[maxn]; 11 inline int read(){ 12 int x=0,f=1; char ch=getchar(); 13 while (ch<‘0‘||ch>‘9‘){if (ch==‘-‘) f=-f; ch=getchar();} 14 while (ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); 15 return x*f; 16 } 17 void add(int x,int y,int z){ 18 nxt[++tot]=lnk[x],son[tot]=y,w[tot]=z,lnk[x]=tot; 19 } 20 void spfa(int fl){ 21 memset(dis[fl],63,sizeof dis[fl]),INF=dis[fl][0]; 22 memset(vis,0,sizeof vis); 23 memset(q,0,sizeof q); 24 dis[fl][fl]=0,vis[fl]=1,q[1]=fl,h=0,t=1; 25 while (h!=t){ 26 h=(h+1)%maxn,vis[q[h]]=0; 27 for (int j=lnk[q[h]]; j; j=nxt[j]) 28 if (dis[fl][son[j]]>dis[fl][q[h]]+w[j]){ 29 dis[fl][son[j]]=dis[fl][q[h]]+w[j]; 30 if (!vis[son[j]]){ 31 t=(t+1)%maxn,q[t]=son[j],vis[son[j]]=1; 32 if (dis[fl][q[(h+1)%maxn]]>dis[fl][q[t]]) swap(q[(h+1)%maxn],q[t]); 33 } 34 } 35 } 36 } 37 int main(){ 38 n=read(),m=read(); 39 for (int i=1; i<=m; i++){ 40 int x=read(),y=read(),z=read(); 41 add(x,y,z),add(y,x,z); 42 } 43 spfa(1),spfa(2),spfa(3); 44 for (int i=1; i<=n; i++) 45 if (!(lnk[i]==0||dis[1][i]==INF||dis[2][i]==INF||dis[3][i]==INF)){ 46 bool flg=1; 47 for (int j=lnk[i]; j; j=nxt[j]){ 48 int pre=son[j]; 49 bool f1=dis[1][i]==dis[1][pre]+w[j],f2=dis[2][i]==dis[2][pre]+w[j],f3=dis[3][i]==dis[3][pre]+w[j]; 50 if (f1+f2+f3>=2) flg=0; 51 } 52 if (flg) ans[++ans[0]]=i; 53 } 54 if (!ans[0]) printf("impossible"); 55 else{ 56 printf("%d\n",ans[0]); 57 for (int i=1; i<=ans[0]; i++) printf("%d ",ans[i]); 58 } 59 return 0; 60 }
派对选址