日记详情

`#include<bits/stdc++.h>
using namespace std;
const int N = 210,INF = 0x3f3f3f3f;
using pr = pair<int,double>;
using pr2 = pair<double,int>;
int n,m;
pair<int,int> node[N];
vector g[N];

double dist[N];
int st[N];
priority_queue<pr2,vector,greater> q;
int pre[N];

// 距离函数
double d(int u,int v)
{
return sqrt((node[u].first-node[v].first)(node[u].first-node[v].first)+(node[u].second-node[v].second)(node[u].second-node[v].second));
}

void dijkstra(int e1,int e2)
{
for(int i=1;i<=n;i++)
{
dist[i]=INF;
}
memset(st,0,sizeof st);
dist[1] = 0;
q.push({0,1});
while(q.size())
{
int t = q.top().second;
q.pop();
if(st[t] == 1)
continue;
st[t] = 1;
for(int i=0;i<g[t].size();i++)
{
int j = g[t][i].first;
double w = g[t][i].second;
// 删边
if(te1 && je2 || te2 && je1)
continue;
if(dist[j] > dist[t]+w)
{
dist[j] = dist[t]+w;
q.push({dist[j],j});
if(e1-1 && e2-1)
pre[j] = t;
}
}
}
}

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>node[i].first>>node[i].second;
}
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
double w = d(u,v);
g[u].push_back({v,w});
g[v].push_back({u,w});
}

dijkstra(-1,-1);

double ans = INF;
for(int i=n;i!=1;i=pre[i])
{
dijkstra(pre[i],i);
ans = min(ans,dist[n]);
}

if(ans == INF)
cout<<-1;
else
printf("%.2f",ans);
return 0;
}`