Dijkstra最短路

佚名 6年前 (2019-04-27) 随笔 618人围观抢沙发百度已收录


#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include <memory.h>
#define INF 0x3f3f3f
using namespace std;
int s,m,n;
int dis[1000];
int vis[1000];
int edge[1000][1000];
int outNum;
void init(){
    memset(dis,0x3f3f3f,sizeof(dis));

    outNum=0;
    for(int i=0;i<n;i++){
        dis[i]=min(dis[i],edge[s][i]);
    }


}

void dijkstra(){
  init();
  dis[s]=0;
  vis[s]=1;
  outNum++;
  while(1){

    int minm=INF,idx;
    for(int i=0;i<n;i++){
        if(!vis[i]&&dis[i]<minm){
            minm = dis[i];
            idx=i;
        }
    }
    vis[idx]=1;
    outNum++;
    if(outNum==n)
        break;
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        dis[i]=min(dis[i],minm+edge[idx][i]);
    }
  }
  for(int i=0;i<n;i++)
  printf("from: %d     to: %d      dis: %d\n",s,i,dis[i]);

}


int main(){
    memset(edge,0x3f3f3f,sizeof(edge));
    cin>>n>>m>>s;
    for(int i=0;i<n;i++){
        edge[i][i]=0;
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        edge[a][b]=edge[b][a]=c;
    }
    dijkstra();
}
/* mock-data 
6 9 0 
0 1 93 
0 4 64 
0 5 6 
1 2 7 
2 5 12
2 3 19 
3 5 2 
3 4 8 
4 5 5 */