题解 | #最短路径#

Dijkstra算法（优先队列优化）

• 输入邻接矩阵的边
• 调用迪杰斯特拉算法：每次选取离源点最近的点作为中介，更新到其余的的距离

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<climits>
using namespace std;

const int maxn=10010;
const int INF=INT_MAX;

struct Point{//优先队列的结点（编号、到源点的距离）
  int number;
  int distance;
  Point(int n,int d):number(n),distance(d){}
  bool operator <(Point x)const{
    return distance>x.distance;
  }
};

struct Edge{//图的边
  int to;
  int lenth;
  Edge(int t,int l):to(t),lenth(l){}
}; 


vector<Edge>graph[maxn];//图的邻接矩阵
int dis[maxn];

void Dijkstra(int start,int n){
  fill(dis+1,dis+n+1,INF);//距离设为无穷大(编号从1开始)
  dis[start]=0;
  priority_queue<Point>myqueue;
  myqueue.push(Point(start,dis[start]));
  while(!myqueue.empty()){
    int u=myqueue.top().number;
    myqueue.pop();
    for(int j=0;j<graph[u].size();j++){//根据新选的u来更新距离
      int v=graph[u][j].to;
      int d=graph[u][j].lenth;
      if(dis[u]+d<dis[v]){
        dis[v]=dis[u]+d;
        myqueue.push(Point(v,dis[v]));
      }
    }
  }
  return;
}

int main(){
  int n,m;
  while(scanf("%d%d",&n,&m)!=EOF){
    int start;
    int terminal;
    scanf("%d%d",&start,&terminal);
    memset(graph,0,sizeof(graph));
    while(m--){
      int from,to,lenth;
      scanf("%d%d%d",&from,&to,&lenth);
      graph[from].push_back(Edge(to,lenth));//有向边
    }
    
    Dijkstra(start,n);
    if(dis[terminal]==INF)dis[terminal]=-1;
    printf("%d\n",dis[terminal]);
  }
  return 0;
}