P1744 写了一半把Dijkstra写完了,后面不知道咋写了,DALAO求救!(听说水区大佬多)
#include <bits/stdc++.h>
using namespace std;
vector<int> e[10001];
vector<int> f[10001];
int vis[10001],x[10001],y[10001];
double dis[10001],w;
int main() {
int n,m,u,v,s,minn,k,t;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>u>>v;
w=sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));
e[u].push_back(v);
f[u].push_back(v);
}
cin>>s>>t;
memset(dis,63,sizeof(dis));
dis[s]=0;
for(int i=1;i<=n;i++) {
minn=0x3f3f3f3f;
for(int j=1;j<=n;j++) {
if(vis[j]==0&&dis[j]<minn) {
minn=dis[j];
k=j;
}
}
vis[k]=1;
if(k==t)break;
for(int j=0;j<e[k].size();j++) {
t=e[k][j];
if(vis[t]==0&&dis[k]+f[k][j]<dis[t])
dis[t]=dis[k]+f[k][j];
}
}
printf("%.2lf",dis[t]);
return 0;
}
%%%