Hdu2680 最短路

时间:2022-04-06 21:00:22

给定一个有向图,多个起点,一个终点,求起点到终点的最短路。

1.可以加一个点,使其与那些起点的距离为0

2.将图反着来建,然后在所有点找出最小的

方案一:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define MaxInt 0x3f3f3f3f
using namespace std;
int Map[1005][1005];
int vis[1005];
int low[1005];
int p[1005];
int n,m,s;
int k;
void work()
{
int pos = 0,Min;
memset(vis,0,sizeof(vis));
for(int i = 0; i <= n; i++)
low[i] = Map[pos][i];
vis[pos] = 1;
for(int i = 0; i < n; i++)
{ Min = MaxInt;
for(int j = 0; j <= n; j++)
if(!vis[j] && low[j] < Min)
{
pos = j;
Min = low[j];
}
if(Min == MaxInt)
break;
vis[pos] = 1;
for(int j = 0; j <= n; j++)
if(!vis[j] && low[j] > low[pos]+Map[pos][j])
low[j] = low[pos]+Map[pos][j];
}
if(low[s] < MaxInt)
printf("%d\n",low[s]);
else
printf("-1\n");
} int main()
{
int a,b,c;
while(~scanf("%d%d%d",&n,&m,&s))
{
for(int i = 0; i <= n; i++)
{
Map[i][i] = 0;
for(int j = 0; j <= n; j++)
Map[i][j] = MaxInt;
}
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(Map[a][b] > c)
Map[a][b]=c;
}
int all,x;
scanf("%d",&all);
for(int i = 1; i <= all; i++){ //加入0点,并使其为起始点
scanf("%d",&x);
Map[0][x] = 0;
}
work();
}
return 0;
}

 

方案二:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MaxInt 0x3f3f3f3f
using namespace std;
int Map[1005][1005];
int vis[1005];
int low[1005];
int p[1005];
int n,m,s;
int k;
void work()
{
int pos = s,Min;
memset(vis,0,sizeof(vis));
for(int i = 0; i <= n; i++)
low[i] = Map[pos][i];
vis[pos] = 1;
for(int i = 0; i < n; i++)
{ Min = MaxInt;
for(int j = 0; j <= n; j++)
if(!vis[j] && low[j] < Min)
{
pos = j;
Min = low[j];
}
if(Min == MaxInt)
break;
vis[pos] = 1;
for(int j = 0; j <= n; j++)
if(!vis[j] && low[j] > low[pos]+Map[pos][j])
low[j] = low[pos]+Map[pos][j];
}
} int main()
{
int a,b,c;
while(~scanf("%d%d%d",&n,&m,&s))
{
for(int i = 0; i <= n; i++)
{
Map[i][i] = 0;
for(int j = 0; j <= n; j++)
Map[i][j] = MaxInt;
}
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(Map[b][a] > c) //反着建图
Map[b][a]=c;
}
work();
int num,x;
int MinInt = MaxInt;
scanf("%d",&num);
for(int i = 1;i <= num;i++)
{
scanf("%d",&x);
if(low[x] < MinInt) //找出最短的路
MinInt = low[x];
}
if(MinInt < MaxInt)
printf("%d\n",MinInt);
else
printf("-1\n");
}
return 0;
}