Demo entry 6353102

dijkstra

   

Submitted by anonymous on Mar 29, 2017 at 07:42
Language: C++. Code size: 1.4 kB.

#include<stdio.h>
#include<string.h>
#define INF 999999999
#include<algorithm>
using namespace std;
int n,m,s;
int dis[1001];
int map[1001][1001];
int vis[1001];
int c;

/*
*dis[i]	表示从起点到相邻点i的距离,如果有多个起点,dis[]可以为0
*vis[]	记录已经访问过的节点
*map[i][j]	表示从节点i到j的距离 
*/ 
void Dijkstra(){
	int u;
	memset(vis,0,sizeof(vis));
	for(int i=0;i<=c;i++){
		dis[i] = map[0][i];	//初始化dis 
	}
	vis[0] = 1;
	int min = INF;
	for(int i=1;i<=c;i++){
		min = INF;
		for(int j=1;j<=c;j++){		//遍历目前起点到其他点的最短距离 
			if(vis[j] == 0 && dis[j] < min){
				min = dis[j];
				u = j;
			}
		}
		vis[u] = 1;
		for(int v=1;v<=c;v++){		//遍历该点到其他点的距离 
			if(map[u][v] < INF){
				if(dis[v] > dis[u] + map[u][v]){
					dis[v] = dis[u] + map[u][v];
				}		//记录从起点到点v的最短距离 
			}
		}	
	}
}
int main(){
	int p,q,t;
	while(~scanf("%d %d %d",&n,&m,&s)){
		
		for(int i=0;i<1001;i++){
			for(int j=0;j<1001;j++){
				map[i][j] = INF;	//节点未连接之前距离无限大 
			}
			map[i][i] = 0;	//自己到自己的距离为0 
		}
		
		for(int i=0;i<m;i++){
			scanf("%d %d %d",&p,&q,&t);
			c = max(max(c,p),q);
			if(t < map[p][q]){
				map[p][q] = t;		//初始化 
			}
		}
		int m,w;
		scanf("%d",&m);
		for(int i=0; i<m; i++){  
            scanf("%d",&w);  
            map[0][w] = 0;			//初始化相邻点 
        }  
        Dijkstra();
        if(dis[s] < INF)
			printf("%d\n",dis[s]);
		else
			printf("-1\n");
	}
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).