2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=205; int p; struct edge{ int to; int next; int val; }a[20005]; int head[N],cnt; void add_edge(int u,int v,int w){ if(u==v) return;//每个牧场由一条条道路和一个或多个牧场连接(可能包括自己) //可以不管重边，dijkstra会解决 a[++cnt].to=v; a[cnt].val=w; a[cnt].next=head[u]; head[u]=cnt; return; //链式前向星存图 } int dis[N]; bool vis[N]; struct node{ int now; int w; bool operator < (const node &S) const { return w>S.w; } }; priority_queue<node>Q; void dijkstra(int start){//模板 for(int i=0;i<=55;i++) dis[i]=1e9; dis[start]=0; Q.push({start,0}); while(!Q.empty()){ int t=Q.top().now; Q.pop(); if(vis[t]) continue; vis[t]=1; for(int i=head[t];i;i=a[i].next){ int to=a[i].to; if(dis[to]>dis[t]+a[i].val){ dis[to]=dis[t]+a[i].val; if(!vis[to]) Q.push({to,dis[to]}); } } } return; } int num(char ch){ if('a'<=ch&&ch<='z') return ch-'a'+26; return ch-'A'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>p; for(int i=1;i<=p;i++){ char ch,ch2;int c; cin>>ch>>ch2>>c; int a=num(ch),b=num(ch2); add_edge(a,b,c);add_edge(b,a,c);//建边 } dijkstra(25); int mi=1e9,mii=0; for(int i=0;i<=24;i++){ if(dis[i]<mi){ mi=dis[i]; mii=i; } }//同理 cout<<char(mii+'A')<<' '<<mi; return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=205; int p; int dp[N][N]; int num(char ch){ if('a'<=ch&&ch<='z') return ch-'a'+26; return ch-'A'; } signed main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>p; for(int i=0;i<=55;i++){ for(int j=0;j<=55;j++){ dp[i][j]=1e9; } }//求最小值，所以初始化为很大的数 for(int i=1;i<=p;i++){ char ch,ch2;int c; cin>>ch>>ch2>>c; int a=num(ch),b=num(ch2); //转成数 dp[a][b]=dp[b][a]=min(dp[a][b],c); //重边取最小值，因为尽量要走短的路 } for(int k=0;k<=55;k++){ for(int i=0;i<=55;i++){ for(int j=0;j<=55;j++){//Floyd求最短路 dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]); } } } int mi=1e9,mii=0; for(int i=0;i<=24;i++){ if(dp[i][25]<mi){//dp[i][25]为第 i 个牧场的奶牛到谷场的距离 mi=dp[i][25]; mii=i;//取最小值并记录 } } cout<<char(mii+'A')<<' '<<mi; //转成奶牛编号（字符）并输出奶牛编号和最短路径 return 0; }
9班陈新华
LV 6
@ 2025-7-4 15:15:48
- 1