提交时间:2024-01-07 15:15:21

运行 ID: 230045

#include<bits/stdc++.h> using namespace std; struct EDGA { int f; int t; int w; }; vector<EDGA>e[100002]; int dis[100002]; bool vis[100002]; int n,s,p; void spfa(int s) { for(int i=1; i<=n; i++) { dis[i]=0x3f3f3f3f; } dis[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0; i<e[u].size(); i++) { int v=e[u][i].t; int w=e[u][i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; q.push(v); } } } } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { int m; scanf("%d",&m); if(i!=n) { EDGA z; z.f=i; z.t=i+1; z.w=m; e[i].push_back(z); z.f=i+1; z.t=i; e[i+1].push_back(z); } else { EDGA z; z.f=1; z.t=n; z.w=m; e[1].push_back(z); z.f=n; z.t=1; e[n].push_back(z); } } scanf("%d%d",&s,&p); spfa(s); printf("%d\n",dis[p]); return 0; }