边权递增最短路
思路就是题解里的思路，主要说一下错误的原因：
- 1.将边权相等的边都处理好后也是要取\(min\)的，虽然是可以更新才放进去的，但还是要取\(min\)，举个例子
当用\(i\,j\)更新\(u\)的时候直接赋值就会出错。
- 2.当\(while\)循环结束时，队列中可能还有元素，要把他们也加进去。
还有就是写\(while\)的话还是一次一次的来吧，如果\(while\)里再写一个\(while\)的话，很可能会炸边界。（参见第一次提交）
(\(while\)的话还是少用吧，边界炸好多次了。
终极版代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define MP make_pair
#define fi first
#define se second
#define u e[i].from
#define v e[i].node
#define LL long long
using namespace std;
const LL N = 100005;
const LL inf = 4557430888798830399;
typedef pair<LL,LL> pll;
LL n,m,tot,dis[N],T,num;
struct edge{
LL node,data,from;
}e[N<<1];
/*struct node{
LL val,id;
}q[N];*/
queue<pll> q;
void add(LL x,LL y,LL z)
{
e[++tot].node=y;
e[tot].from=x;
e[tot].data=z;
}
bool cmp(const edge &x,const edge &y)
{ return x.data<y.data; }
void solve()
{
memset(dis,0x3f,sizeof(dis));
scanf("%lld%lld",&n,&m);
dis[1]=0; tot=0; num=0;
LL x,y,z,last=0;
for(LL i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
}
sort(e+1,e+tot+1,cmp);
/* for(LL i=1;i<=tot;i++)
{
if(e[i].data!=e[i-1].data)
{
while(!q.empty())
{
dis[q.front().se]=min(q.front().fi,dis[q.front().se]);
q.pop();
}
}
if(dis[u]>dis[v]+e[i].data)
q.push(MP(dis[v]+e[i].data,u));
if(dis[v]>dis[u]+e[i].data)
q.push(MP(dis[u]+e[i].data,v));
}
while(!q.empty())
dis[q.front().se]=min(q.front().fi,dis[q.front().se]),q.pop();*/
LL i=1;
while(i<=tot)
{
if(e[i].data==e[i-1].data)
{
if(dis[u]>dis[v]+e[i].data)
q.push(MP(dis[v]+e[i].data,u));
if(dis[v]>dis[u]+e[i].data)
q.push(MP(dis[u]+e[i].data,v));
}
else
{
while(!q.empty())
{
LL j=q.front().se,k=q.front().fi;
dis[j]=min(k,dis[j]); q.pop();
}
if(dis[u]>dis[v]+e[i].data)
q.push(MP(dis[v]+e[i].data,u));
if(dis[v]>dis[u]+e[i].data)
q.push(MP(dis[u]+e[i].data,v));
}
++i;
/*bool flag=0;
while(e[i+1].data==e[i].data)
{
flag=1;
if(dis[u]>dis[v]+e[i].data)
q.push(MP(dis[v]+e[i].data,u));
if(dis[v]>dis[u]+e[i].data)
q.push(MP(dis[u]+e[i].data,v));
++i;
}
if(flag)
{
if(dis[u]>dis[v]+e[i].data)
q.push(MP(dis[v]+e[i].data,u));
if(dis[v]>dis[u]+e[i].data)
q.push(MP(dis[u]+e[i].data,v));
++i;
}
while(!q.empty())
{
LL j=q.front().se,k=q.front().fi;
dis[j]=min(k,dis[j]); q.pop();
}
if(!flag)
{
if(dis[u]>dis[v]+e[i].data)
dis[u]=dis[v]+e[i].data;
if(dis[v]>dis[u]+e[i].data);
dis[v]=dis[u]+e[i].data;
++i;
}*/
}
while(!q.empty())
{
LL j=q.front().se,k=q.front().fi;
dis[j]=min(k,dis[j]); q.pop();
}
if(dis[n]==inf) printf("No answer\n");
else printf("%lld\n",dis[n]);
return ;
}
int main()
{
scanf("%lld",&T);
while(T--) solve();
return 0;
}