#include<bits/stdc++.h>
using namespace std;
int h[500001],nxt[1000001],val[1000001],zd[1000001],cnt=0;
int n,m,s;
long long dis[500001];
bool inq[500001];
int q[10000001],f,e;
void addedge(int a,int b,int c){
    cnt++;
    val[cnt]=c,zd[cnt]=b,nxt[cnt]=0;
    nxt[cnt]=h[a];
    h[a]=cnt;
}
signed main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b,c);
    }
    memset(dis,-1,sizeof(dis));
    dis[s]=0,inq[s]=1;
    q[1]=s,f=1,e=1;
    while(f<=e){
        int u=q[f++];
        for(int p=h[u];p;p=nxt[p]){
            int v=zd[p],c=val[p];
            if(dis[v]==-1||dis[v]>dis[u]+c){
                dis[v]=dis[u]+c;
                if(inq[v]==0)q[++e]=v,inq[v]=1;
            }
        }
        inq[u]=0;
    }
    for(int i=1;i<=n;i++){
        if(dis[i]!=-1)printf("%d ",dis[i]);
        else printf("-1 ");
    }
}

写了个 SPFA 过不了，求助 /kk

有没有大神能解答一下 UER、UTR、UNR 大致是什么难度啊，谢谢！

我觉得这道题就是个最短路，SPFA 跑 $n$ 遍应该略大于 $O(n^2)$，模拟赛时间不够，我采用了 Floyd，然后加上一个 $O(n^4)$ 的枚举，采用分讨略微优化一点时间，感觉可以排序大幅减少枚举次数，求大神帮助剪枝，thx。

我的代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
bool ed[10001][10001];
int zhuan[10001][10001];
long long val[2512];
bool cmp(long long a,long long b){
    return a>b;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    memset(zhuan,-1,sizeof(zhuan));
    for(register int i=1;i<n;i++)cin>>val[i];
    for(register int i=0;i<m;i++){
        register int fr,to;
        cin>>fr>>to;
        ed[fr-1][to-1]=1;//数据较小，邻接矩阵存边比前向星快
        ed[to-1][fr-1]=1;
        zhuan[fr-1][to-1]=0;
        zhuan[to-1][fr-1]=0;
    }
    if(k==0){
        unsigned long long res=0;
        for(register int a=1;a<n;a++){//枚举
            for(register int b=1;b<n;b++){
                if(b==a)continue;
                for(register int c=1;c<n;c++){
                    if(c==a||c==b)continue;
                    for(register int d=1;d<n;d++){
                        if(d==a||d==b||d==c)continue;
                        if(ed[0][a]==1){
                            if(ed[a][b]==1){
                                if(ed[b][c]==1){
                                    if(ed[c][d]==1){
                                        if(ed[d][0]==1){
                                            if(val[a]+val[b]+val[c]+val[d]>res){//因为没有预处理转车，肯定转车次数为0
                                                res=val[a]+val[b]+val[c]+val[d];
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        cout<<res;
    }else{
        for(register int a=0;a<n;a++){//跑Floyd（Floyed）
            for(register int b=0;b<n;b++){
                if(b==a)continue;
                for(register int c=0;c<n;c++){
                    if(c==a||c==b)continue;
                    if(ed[a][b]&&ed[b][c]){
                        ed[a][c]=1;
                        if(zhuan[a][c]==-1||zhuan[a][b]+zhuan[b][c]+1<zhuan[a][c])zhuan[a][c]=zhuan[a][b]+zhuan[b][c]+1;//计算转车次数
                    }
                }
            }
        }
        unsigned long long res=0;
        for(register int a=1;a<n;a++){//枚举
            for(register int b=1;b<n;b++){
                if(b==a)continue;
                for(register int c=1;c<n;c++){
                    if(c==a||c==b)continue;
                    for(register int d=1;d<n;d++){
                        if(d==a||d==b||d==c)continue;
                        if(ed[0][a]==1){
                            if(ed[a][b]==1){
                                if(ed[b][c]==1){
                                    if(ed[c][d]==1){
                                        if(ed[d][0]==1){
                                            if(zhuan[0][a]>k||zhuan[a][b]>k||zhuan[b][c]>k||zhuan[c][d]>k||zhuan[d][0]>k)continue;//转车不能多于k次
                                            if(val[a]+val[b]+val[c]+val[d]>res){
                                                res=val[a]+val[b]+val[c]+val[d];
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        cout<<res;
    }
}

我觉得优化下可以比 $45$ 分多，感激不尽！

我们可不可以使用若干个队列存储数列中有序的子序列，然后用线段树维护队首，每次比较队首求最小值，直到所有队列为空。

这种排序算法似乎时间复杂度最好 $O(n)$，最坏 $O(n \log n)$。

我注册 SPOJ，一直显示“wrong or unfilled captcha”，请问是什么情况

题面：

【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

输出格式

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1

样例输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

样例输出 #1

4
4
1
4
4

提示

对于 $30\%$ 的数据，$N\leq 10$，$M\leq 10$。

对于 $70\%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100\%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，不保证 $a \neq b$。

样例说明：

该树结构如下：

第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。

第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。

第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。

第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。

第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4, 4, 1, 4, 4$。

我用的是链式存储结构，WA了。

#include<bits/stdc++.h>
using namespace std;
class tzx{
    public:
        int sc,jl;
};
class node{
    public:
        node();
        int p,q,parent,son[1001];
        tzx zx[1001];
};
node tree[100001];
int n,m,r;
node::node(){
    p=0;
    q=0; 
}
void dfs(int q,int p,int jl){
    if(tree[q].p==0)return;//没有子树就结束 
    tree[p].zx[tree[p].q++].sc=q;
    tree[p].zx[tree[p].q++].jl=jl;
    for(int i=0;i<tree[p].p;i++){
        dfs(q,tree[p].son[i],jl+1);
    }
}
int main(){
    cin>>n>>m>>r;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        tree[x].parent=y;
        tree[y].son[tree[y].p++]=x;
    }
    for(int i=1;i<=n;i++){
        dfs(i,i,0);//自己也是自己的祖先 
    }
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)cout<<x<<"\n";
        else{
            int ans=0,mn=INT_MAX;
            for(int j=0;j<tree[x].q;j++)
                for(int k=0;k<tree[y].q;k++){
                    if(tree[x].zx[j].sc==tree[y].zx[k].sc){
                        if(tree[x].zx[j].jl+tree[y].zx[k].jl<mn){
                            mn=tree[x].zx[j].jl+tree[y].zx[k].jl;
                            ans=tree[x].zx[j].sc;
                        }
                    }
                }
            cout<<ans<<"\n";
        }
    }
}

题目描述

有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量多。

输入格式

第1行，一个整数N，表示城市数。

第2行到第n+1行，每行两个整数，中间用一个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式

仅一行，输出一个整数，表示政府所能批准的最多申请数。

输入输出样例

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

4

说明/提示

50% 1<=N<=5000,0<=xi<=10000

100% 1<=N<=2e5,0<=xi<=1e6

出处：NOJ 1926 http://39.98.219.132/contest/2191/problem/1926

float InvSqrt(float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;       // get bits for floating value
    i = 0x5f3759df - (i>>1); // gives initial guess y0
    x = *(float*)&i;         // convert bits back to float
    x = x*(1.5f-xhalf*x*x);  // Newton step, repeating increases accuracy
    return x;
}

转自：https://www.zhihu.com/question/37692782/answer/73323805