AC#1#6，36分求助DIj(c++)

本人的提交记录： 代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
using namespace std;
priority_queue<pair<int,int> >q;
const int MAXN = 1e5 + 15;
const int MR = 2e5 + 15;
const int INF = 0x7f7f7f7f;
int n,m,p,s;
struct rd{
    int u;
    int v;
    int w;
};
rd b[MR];
int c[MAXN];
int head[MAXN];
int last[MAXN];
//邻接表 
struct edge{
    int to;
    int last;
    int wei;
    //权 
};
edge d[MR];
bool vis[MAXN];
int ans[MAXN];
struct node{
    int ans;
    int id;
    bool operator <(const node &x)const{
        //借鉴user113401的题解写的 
        return (x.ans>ans);
    }
};
priority_queue<node>q2;
void spfa(int a){
    int x = a;
    q.push(make_pair(x,0));
    pair<int,int>k;
    while(!q.empty()){
        k = q.top();
        q.pop();
        for(int i = 1;i<=p;i++){
            if(b[i].u==k.first){
                if(c[b[i].v]>b[i].w+k.second){
                    c[b[i].v] = b[i].w + k.second;
                    q.push(make_pair(b[i].v,c[b[i].v]));
                }
            }
        }
    }
    for(int i = 1;i<=n;i++){
        printf("%d ",c[i]);
    }
    return ;
}
void method_1(){
    scanf("%d%d%d",&n,&m,&s);
    p = 0;
    for(int i = 1;i<=m;i++){
        int tmp1,tmp2,tmp3;
        scanf("%d%d%d",&tmp1,&tmp2,&tmp3);
        if(tmp1!=tmp2){
            p++;
            b[p].u = tmp1;
            b[p].v = tmp2;
            b[p].w = tmp3;
        }
    }
    memset(c,INF,sizeof(c));
    c[s] = 0;
    spfa(s);
    return ;
}
void dijkstra1(int a){
    int pos;
    pos = a;
    while(vis[pos]==false){
        vis[pos] = true;
        for(int i = head[pos];i!=0;i = d[i].last){
            if(!vis[d[i].to]&&ans[d[i].to]>ans[pos] + d[i].wei){
                ans[d[i].to] = ans[pos] + d[i].wei;
            }
        }
        int minn;
        minn = 0x7fffffff;
        for(int i = 1;i<=n;i++){
            if(!vis[i]&&minn>ans[i]){
                minn = ans[i];
                pos = i;
                //找最小的 
            }
        }
    }
    return ;
}
void method_2(){
    scanf("%d%d%d",&n,&m,&s);
    int tmp1,tmp2,tmp3;
    p = 0;
    memset(head,0,sizeof(head));
    for(int i = 1;i<=m;i++){
        scanf("%d%d%d",&tmp1,&tmp2,&tmp3);
        if(tmp1!=tmp2){
            p++;
            if(head[tmp1]==-1){
                head[tmp1] = i;
                //头一个 
            }
            d[p].to = tmp2;
            d[p].wei = tmp3;
            d[p].last = last[tmp1];
            last[tmp1] = p;
        }
    }
    memset(vis,false,sizeof(vis));
    memset(ans,INF,sizeof(ans));
    ans[s] = 0;
    dijkstra1(s);
    for(int i = 1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return ;
}
void dijkstra2(int a){
    int pos;
    pos = a;
    node tmp4;
    tmp4.ans = 0;
    tmp4.id = a;
    q2.push(tmp4);
    while(!q2.empty()){
        if(!vis[pos]){
        vis[pos] = true;
        for(int i = head[pos];i!=0;i = d[i].last){
            if(ans[d[i].to]>ans[pos] + d[i].wei){
                ans[d[i].to] = ans[pos] + d[i].wei;
                if(!vis[d[i].to]){
                    node tmp;
                    tmp.ans = -ans[d[i].to];
                    tmp.id = d[i].to;
                    q2.push(tmp);
                }
            }
        }
        }
        q2.pop();
        pos = q2.top().id;
    }
    return ; 
}
void method_3(){
    scanf("%d%d%d",&n,&m,&s);
    int tmp1,tmp2,tmp3;
    p = 0;
    memset(head,0,sizeof(head));
    memset(last,0,sizeof(last));
    for(int i = 1;i<=m;i++){
        scanf("%d%d%d",&tmp1,&tmp2,&tmp3);
        if(tmp1!=tmp2){
            p++;
            head[tmp1] = i;
            //最后一个 
            d[p].to = tmp2;
            d[p].wei = tmp3;
            d[p].last = last[tmp1];
            last[tmp1] = p;
            //printf("TEST");
        }
    }
    memset(vis,false,sizeof(vis));
    memset(ans,INF,sizeof(ans));
    ans[s] = 0;
    dijkstra2(s);
    for(int i = 1;i<=n;i++){
        if(ans[i] == INF){
            cout << 2147483647 << " ";
        }
        else {
            printf("%d ",ans[i]);
        }
    }
    return ;
}
int main(){
    //method_1();
    //method_2();
    method_3();
    return 0;
}

method_3()36分;

弱化版0分，又T又WA

method_1(),spfa全T;

弱化版60分，4个WA;

method_2(),朴素dijkstra,代码;

求调