#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”，请问是什么情况