提交时间:2024-01-07 15:05:31

运行 ID: 230027

#include<bits/stdc++.h> using namespace std; int f[2502][2502];//是否通 int dis[2502]; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;//小跟堆 距离+编号 bool v[2502]; int n,s,e; void dj() { q.push(make_pair(0,s)); while(!q.empty()) { int u=q.top().second; q.pop(); if(v[u]) continue; v[u]=true; for(int i=1; i<=n; i++) { if(dis[u]+f[u][i]<=dis[i]) { dis[i]=dis[u]+f[u][i]; q.push(make_pair(dis[i],i)); } } } } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) f[i][j]=0x3f3f3f3f; for(int i=1; i<n; i++) { scanf("%d",&f[i][i+1]); f[i+1][i]=f[i][i+1]; } scanf("%d",&f[n][1]); f[1][n]=f[n][1]; scanf("%d%d",&s,&e); for(int i=1; i<=n; i++) dis[i]=f[s][i]; dis[s]=0; dj(); printf("%d\n",dis[e]); return 0; }