【链接】http://acm.hdu.edu.cn/showproblem.php?pid=6181
【题意】
让你求从1到n的次短路
【题解】
模板题;
因为点可以重复走;
则一定会有次短路。
dijkstra算法+优先队列优化一下就好.
【错的次数】
11+
【反思】
在写优先队列的时候,节点和路径长度写反了..应该节点写在后面才行的。。
【代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define Open() freopen("F:\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
#define sz(x) ((int) x.size())
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
mt19937 myrand(time(0));
int get_rand(int n){return myrand()%n + 1;}
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
struct abc{
int en,nex;
LL w;
};
int n,m;
LL dis[N+10][2];
priority_queue <pll ,vector <pll> ,greater<pll> > dl;
vector <pii> G[N+10];
int main(){
//Open();
//Close();
int T;
ri(T);
while (T--){
ri(n),ri(m);
rep1(i,1,n) G[i].clear();
rep1(i,1,m){
int a,b; LL w;
ri(a),ri(b),rl(w);
G[a].pb(mp(b,w));
G[b].pb(mp(a,w));
}
ms(dis,INF);
dis[1][0] = 0;
dl.push(mp(0,1));
while (!dl.empty()){
LL d = dl.top().fi,x = dl.top().se;
dl.pop();
if (dis[x][1] < d) continue;
int len = sz(G[x]);
rep1(i,0,len-1){
LL y = G[x][i].fi,cost = d + G[x][i].se;
if (dis[y][0] > cost){
dis[y][1] = dis[y][0];
dis[y][0] = cost;
dl.push(mp(dis[y][0],y));
}
else if (dis[y][1] > cost){
dis[y][1] = cost;
dl.push(mp(dis[y][1],y));
}
}
}
ol(dis[n][1]);puts("");
}
return 0;
}