# 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.