这几天做的第二道这种路的类型不一样,分策略进行松弛的最短路题,这道和上一道就是一模一样
给出m条路,有car的walk的,要使walk尽量小的情况下再使总路途最小
核心就是Dijk的队列节点要维护两个权值,然后优先级是walk的优先,然后松弛的时候要分情况

#include <bits/stdc++.h>
using namespace std;
#define bug printf("BUG\n")
const int N=4050;
const int M=80050;
const int INF=0x3f3f3f3f;
struct Edge{
   
    int v,w,next;
    bool isWalk;
}edge[M];
int cnt;
int head[N];
void init(){
   
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addEdge(int u,int v,int w,int ch){
   
    bool isWalk;
    if(ch==1){
   
        isWalk=true;
    }
    else{
   
        isWalk=false;
    }
    edge[cnt]=Edge{
   v,w,head[u],isWalk};
    head[u]=cnt++;
    edge[cnt]=Edge{
   u,w,head[v],isWalk};
    head[v]=cnt++;
}
int n,m,p;
int u,v,w;
int s,t;
int isWalk;
int walk[N],sum[N];
bool vis[N];
struct node{
   
    int v,o,s;
    bool operator <(const node &r)const{
   
        //先优先walk小的
        if(o!=r.o){
   
            return o>r.o;
        }
        return s>r.s;
    }
};
void Dijkstra(int s){
   
    for(int i=1;i<=n;i++){
   
        vis[i]=false;
        walk[i]=INF;
        sum[i]=INF;
    }
    walk[s]=0;
    sum[s]=0;
    priority_queue<node> q;
    q.push(node{
   s,0,0});
    node tmp;
    while(!q.empty()){
   
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        if(vis[u]){
   
            continue;
        }
        vis[u]=true;
        for(int i=head[u];i!=-1;i=edge[i].next){
   
            int v=edge[i].v;
            int w=edge[i].w;
            bool flag=edge[i].isWalk;
            //这一段不是步行的
            if(!flag){
   
            	//步行的dis需要更新,总的也要更新
                if(walk[v]>walk[u]){
   
                    walk[v]=walk[u];
                    sum[v]=sum[u]+w;
                }
                //不行不需要更新,总的更新
                else if(walk[v]==walk[u] && sum[v]>sum[u]+w){
   
                    sum[v]=sum[u]+w;
                }
            }
            //步行的路
            else{
   
            	//注意这里要加上w,因为这一段是步行的
            	//步行和总dis都要更新
                if(walk[v]>walk[u]+w){
   
                    walk[v]=walk[u]+w;
                    sum[v]=sum[u]+w;
                }
                //只更新总dis
                else if(walk[v]==walk[u]+w && sum[v]>sum[u]+w){
   
                    sum[v]=sum[u]+w;
                }
            }
            q.push(node{
   v,walk[v],sum[v]});
        }
    }
}
int T;
int main(void){
   
    scanf("%d",&T);
    while(T--){
   
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<m;i++){
   
            scanf("%d%d%d%d",&u,&v,&w,&isWalk);
            addEdge(u,v,w,isWalk);
        }
        scanf("%d%d",&s,&t);
        memset(walk,0,sizeof(walk));
        memset(sum,0,sizeof(sum));
        Dijkstra(s);
        if(sum[t]!=INF){
   
            printf("%d %d\n",walk[t],sum[t]);
        }
        else{
   
            printf("-1\n");
        }
    }
    return 0;
}