UESTC 915 -- 方老師的分身 II （spfa，dijkstra）

題目大意：求從一個點到另一個點至少經過k條路徑的最短路徑長度；

思路分析：用兩個變量u和e來維護一個點的dis，u表示目前點的編号，e表示經過多少條邊，dis[u][e] 表示走到u點經過e條邊的最短路徑長度，因為是至少是k條邊，是以大于k條邊的當做是k條邊來處理就好了。

代碼實作：

SPFA：

#include<cstdio>
#include<cstring>
#include<queue>
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,S,T,K,top,dis[5005][55];
bool vis[5005][55];
struct Node{
    int v1,va;
    Node *next;
}*h[5005],e[200005];
struct Status{
    int v1,k;
    Status(int _v1=0,int _k=0):v1(_v1),k(_k){}
};
void Addedge(int from,int to,int val){
    Node *p=&e[top++];
    p->v1=to;
    p->va=val;
    p->next=h[from];
    h[from]=p;
}
void Spfa(){
    queue<Status> q;
    dis[S][0]=0;
    q.push(Status(S,0));
    Status head;
    int tmp;
    while(!q.empty()){
        head=q.front();
        q.pop();
        vis[head.v1][head.k]=0;
        for(Node *p=h[head.v1];p;p=p->next){
            tmp=head.k+1;
            tmp=Min(tmp,K);
            if(dis[p->v1][tmp]>dis[head.v1][head.k]+p->va){
                dis[p->v1][tmp]=dis[head.v1][head.k]+p->va;
                if(!vis[p->v1][tmp]){
                    vis[p->v1][tmp]=1;
                    q.push(Status(p->v1,tmp));
                }
            }
        }
    }

}
int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(h,0,sizeof(h));
        memset(vis,0,sizeof(vis));
        memset(dis,0x3f,sizeof(dis));
        top=0;
        int a,b,val;
        while(m--){
            scanf("%d%d%d",&a,&b,&val);
            Addedge(a,b,val);
            Addedge(b,a,val);
        }
        scanf("%d%d%d",&S,&T,&K);
        Spfa();
        int res;
        if(dis[T][K]<INF) printf("%d\n",dis[T][K]);
        else printf("-1\n");
    }
}



           

Dijkstra：注意鄰接表用的結構體和優先隊列用的結構體一定要分開寫，不然記憶體會超的！！！

#include<cstdio>
#include<cstring>
#include<queue>
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,S,T,K,top,dis[5005][55];
bool vis[5005][55];
struct Node{
    int v1,va;
    Node *next;
}*h[5005],e[200005];
struct Status{
    int v1,va,k;
    Status(int _v1=0,int _va=0,int _k=0):v1(_v1),va(_va),k(_k){}
    bool operator<(const Status rhs)const{
        return va>rhs.va;
    }
};
void Addedge(int from,int to,int val){
    Node *p=&e[top++];
    p->v1=to;
    p->va=val;
    p->next=h[from];
    h[from]=p;
}
void Dijkstra(){
    priority_queue<Status> q;
    //memset(dis[S],0,sizeof(dis[S]));
    dis[S][0]=0;
    q.push(Status(S,0,0));
    Status head;
    int tmp;
    while(!q.empty()){
        head=q.top();
        q.pop();
        if(head.v1==T&&head.k==K) break;
        vis[head.v1][head.k]=1;
        for(Node *p=h[head.v1];p;p=p->next){
            tmp=head.k+1;
            tmp=Min(tmp,K);
            if(!vis[p->v1][tmp]&&dis[p->v1][tmp]>dis[head.v1][head.k]+p->va){
                dis[p->v1][tmp]=dis[head.v1][head.k]+p->va;
                q.push(Status(p->v1,dis[p->v1][tmp],tmp));
            }
            //else p->k--;
        }
    }

}
int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(h,0,sizeof(h));
        memset(vis,0,sizeof(vis));
        memset(dis,0x3f,sizeof(dis));
        top=0;
        int a,b,val;
        while(m--){
            scanf("%d%d%d",&a,&b,&val);
            Addedge(a,b,val);
            Addedge(b,a,val);
        }
        scanf("%d%d%d",&S,&T,&K);
        Dijkstra();
        int res;
        /*for(int i=K;i<50;i++){
            if(dis[T][i]<INF){
                res=dis[T][i];
                flag=1;
                break;
            }
        }*/
        //res=Min(dis[T][K],dis[T][K+1]);
        /*for(int i=1;i<=n;i++){
            printf("%d: ",i);
            for(Status *p=h[i];p;p=p->next) printf("%d %d ",p->v1,p->va);
            printf("\n");
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<K+2;j++) printf("%d ",dis[i][j]);
            printf("\n");
        }*/
        if(dis[T][K]<INF) printf("%d\n",dis[T][K]);
        else printf("-1\n");
    }
}