话不多说，邻接表+队列优化。

#include <cstdio>

#include <iostream>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <queue>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAXN=1000010;

const int MAXE=1000010;

struct qnode

{

    int v;

    int c;

    qnode(int _v=0,int _c=0):v(_v),c(_c){}

    bool operator <(const qnode &r)const

    {

        return c>r.c;

    }

};

struct Edge

{

    int v,cost;

    int next;

};

Edge edge[MAXE];

int head[MAXN];

bool vis[MAXN];

int dist[MAXN];

int tot;

int n,m;

priority_queue<qnode>que;

void Dijkstra(int start,int n)//点的编号从1开始

{

    dist[start]=0;

    que.push(qnode(start,0));

    qnode tmp;

    while(!que.empty())

    {

        tmp=que.top();

        que.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 cost=edge[i].cost;

            if(!vis[v]&&dist[v]>dist[u]+cost)

            {

                dist[v]=dist[u]+cost;

                que.push(qnode(v,dist[v]));

            }

        }

    }

}

void addedge(int u,int v,int w)

{

    edge[tot].v=v;

    edge[tot].cost=w;

    edge[tot].next=head[u];

    head[u]=tot;

    tot++;

}

void init()

{

    tot=0;

    memset(edge,0,sizeof(edge));

    memset(head,-1,sizeof(head));

    memset(vis,false,sizeof(vis));

    for(int i=1;i<=n;i++)dist[i]=INF;

    while(!que.empty())que.pop();

}

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        init();

        for(int i=0;i<m;i++){

            int from,to,cost;

            scanf("%d%d%d",&from,&to,&cost);

            addedge(from,to,cost);

        }

        Dijkstra(1,n);//答案在dist数组中

    }

    return 0;

}

 

LL spfa(int s,int t){    for(int i=0; i
     

q; q.push(s); dis[s]=0; vis[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(dis[v]>dis[u]+edge[i].c) { dis[v]=dis[u]+edge[i].c; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[t];}