P1744 DALAO求救!
  • 板块灌水区
  • 楼主Aakw_Tea
  • 当前回复0
  • 已保存回复1
  • 发布时间2024/1/9 20:39
  • 上次更新2024/1/10 10:27:50
查看原帖
P1744 DALAO求救!
1211960
Aakw_Tea楼主2024/1/9 20:39

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;
}

%%%

2024/1/9 20:39
加载中...