题解 P2910 【[USACO08OPEN]寻宝之路Clear And Present Danger】
为啥各位都要用弗洛伊德
居然只有一位大佬用dijkstra...这题没有负边权，多好的一个dijkstra变式题。。。
然后我的脑回路比较清奇，三七二十一地一个一个点地求最短路然后加起来，可能是这个方法太弱智各位大佬都不想用，所以貌似没有这种题解。
于是本蒟蒻斗胆写一篇
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int g[101][101],n,m,dij,minn;
int list[10001],dis[101];
bool vis[101];
int dijkstra(int curr,int end)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++) dis[i]=2e9;
dis[curr]=0;
while(!vis[end])
{
vis[curr]=true;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(dis[curr]+g[curr][i]>=dis[i]) continue;
dis[i]=dis[curr]+g[curr][i];
}
minn=2e9;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
if(minn>=dis[i])
{
minn=dis[i];
curr=i;
}
}
}
return dis[end];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d",&list[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&g[i][j]);
for(int i=1;i<m;i++)
dij+=dijkstra(list[i],list[i+1]);
printf("%d",dij);
return 0;
}