神坑的题目
思路就是枚举起点,迪杰斯特拉求最短路径,再枚举终点(如果起点终点一起枚举可能会超时,也能勉强扯上动态规划的思想吧),求最短路径。
如果剪枝可以加一个变量存最大的点,这样就不用每一次都循环到数据边界1000。
由于对自己很有自信,这题没有用模板写(事实是算法部分也没错,题目重边太坑),代码功能没分函数,整体有点乱。我是括号小王子O(∩_∩)O。
#include<iostream>
#include<cstring>
using namespace std;
#define MAX 0xfffffff;//数据很刁钻,我一开始写2100000000都过不了
int map[1001][1001];
bool vis[1001];
int dis[1001];
int st[1001];
int e[1001];
int main()
{
int t,s,d;
int i,j,k;
while(cin>>t>>s>>d)
{
int mintime=INT_MAX;
for(i=1;i<=1000;i++)
for(j=1;j<=1000;j++)
map[i][j]=MAX;
for(i=1;i<=1000;i++)
map[i][i]=0;
while(t--)
{
int a,b,c;
cin>>a>>b>>c;
if(map[a][b]>c)
map[a][b]=map[b][a]=c;//坑点所在:会有重复的边
}
for(i=1;i<=s;i++)
{
cin>>st[i];
}
for(i=1;i<=d;i++)
{
cin>>e[i];
}
for(i=1;i<=s;i++)
{
memset(vis,false,sizeof(vis));
vis[st[i]]=true;
for(j=1;j<=1001;j++)
dis[j]=map[st[i]][j];
dis[st[i]]=0;
int pos;
for(j=1;j<=1000;j++)
{
int min=MAX;
for(k=1;k<=1000;k++)
{
if(!vis[k] && dis[k]<min)
{
min=dis[k];
pos=k;
}
}
vis[pos]=true;
for(k=1;k<=1000;k++)
{
if(!vis[k] && dis[k]>dis[pos]+map[pos][k])
{
dis[k]=dis[pos]+map[pos][k];
}
}
}
for(j=1;j<=d;j++)
{
if(dis[e[j]]<mintime)
{
mintime=dis[e[j]];
}
}
}
cout<<mintime<<endl;
}
return 0;
}