dijkstra 算法及其队列优化
#include <iostream>#include<bits/stdc++.h>using namespace std;#define maxn 2999//dijkstra 算法的优先队列优化#define inf 999999struct node{ int num,val; //存放结点编号和到初始点的距离}nod;PRiority_queue<node>QQ;//优先从小到大bool Operator < (node a,node b){ if(a.val==b.val) return a.num>b.num; return a.val>b.val;}int book[1000]; //检查这个点是否用过int dis[100]; //到原点最短距离int tu[100][100];//记录路径长度 int n,m;int main(){ int a,b,c; while(~scanf("%d%d",&n,&m)) //输入顶点数和边数 { while(!qq.empty())qq.pop(); memset(book,0,sizeof(book)); memset(tu,-1,sizeof(tu)); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); tu[a][b] = tu[b][a] = c; } for(int i=2;i<=n;i++) dis[i] = inf; dis[1] = 0; nod.num = 1; nod.val = 0; qq.push(nod); while(!qq.empty()) { int t = qq.top().num; qq.pop(); for(int i=2;i<=n;i++) { if(tu[t][i]!=-1&&dis[i]>dis[t]+tu[t][i]) { dis[i] = dis[t] +tu[t][i]; nod.num = i; nod.val = dis[i]; qq.push(nod); } } } for(int i=1;i<=n;i++) { printf("%d ",dis[i]); } } return 0;}新闻热点
疑难解答
