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;}新聞熱點
疑難解答
