因为之前做过这个题。所以这次知道这道题有重边。这次dijkstra的写法加入了优先队列的优化
优先队列 结构体从小到大顺序的两种重载运算符的方式
bool operator <(const Time& a,const Time& b){
return a.start > b.start;
} //这里以大于重载小于是因为默认情况下，优先队列是以大的作为队首，这样一反，就可以再默认情况下使得小的作为队首 struct Time{
int start, end;
bool operator < (const Time& t)const{
return start > t.start;
}
}; 对于从大到小结构体重载运算符的方式照上例
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const double Pi=3.14159265358979323846;
typedef long long ll;
const int MAXN=+;
const int dx[]={,,,-};
const int dy[]={,-,,};
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll mod=1e9+;
struct qnode{
int to,d;
bool operator <(const qnode &r)const{
return d>r.d;
}
//运算符的重载
};
struct Graph {
int weight;
int arcs[MAXN][MAXN];
}G;
int dis[MAXN];
void dijkstra(int v,int n)
{ int U[MAXN];
priority_queue <qnode> Q;
for(int i=;i<=n;i++)
{
U[i]=;
}
for(int i=;i<=n;i++)
{
dis[i]=INF;
}
dis[v]=;
qnode tmp;
tmp.to=v;tmp.d=;
Q.push(tmp);
//这样的没法用优先队列优化，因为没有保留to的值，必须保留才行 while(!Q.empty())
{ tmp=Q.top();Q.pop();
int u=tmp.to;
if(U[u]) continue;
U[u]=;
for(int i=;i<=n;i++)
{
if(U[i]==&&G.arcs[u][i]>&&dis[i]>dis[u]+G.arcs[u][i])
{
dis[i]=dis[u]+G.arcs[u][i];
tmp.d=dis[i];tmp.to=i;
Q.push(tmp);
}
} } } int main()
{
int n,t;scanf("%d%d",&t,&n);
for(int i=;i<=t;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(G.arcs[a][b]!=&&c>G.arcs[a][b])
continue;
else
{
G.arcs[a][b]=c;
G.arcs[b][a]=c;
}
}
dijkstra(n,n);
int ans=dis[];
cout <<ans<<endl;
return ;
}
加油！加油！加油！