P1529 [USACO2.4]回家 Bessie Come Home
home 回家
2023-09-11 14:15:53 时间
https://www.luogu.com.cn/problem/P1529
小坑:要是无向图直接闭眼双向存边,不用多想
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int inf=0x7fffffff;
struct node
{
int to,dis,nxt;
}e[maxn];
int n,head[maxn],val,cnt,minn,s;
ll dist[maxn];
bool vis[maxn];
char c1,c2;
void add_edge(int from,int to,int dis)
{
e[++cnt].to=to;
e[cnt].dis=dis;
e[cnt].nxt=head[from];
head[from]=cnt;
}
void dijkstra()
{
dist[s]=0;
while(!vis[s])
{
vis[s]=1;minn=inf;
for(int i=head[s];i!=-1;i=e[i].nxt)
{
int y=e[i].to;
if(dist[y]>dist[s]+e[i].dis&&!vis[y])
{
dist[y]=dist[s]+e[i].dis;
}
}
for(int i=1;i<=52;i++)
{
if(minn>dist[i]&&!vis[i])
{
minn=dist[i];
s=i;
}
}
}
}
int main()
{
scanf("%d",&n);
head[0]=-1;
for(int i=1;i<=52;i++)
head[i]=-1,dist[i]=inf;
for(int i=1;i<=n;i++)
{
scanf("%s%s%d",&c1,&c2,&val);
int x,y;
if(c1>='A'&&c1<='Z')
x=int(c1-'A')+1;
else if(c1>='a'&&c2<='z')
x=int(c1-'a')+27;
if(c2>='A'&&c2<='Z')
y=int(c2-'A')+1;
else if(c2>='a'&&c2<='z')
y=int(c2-'a')+27;
add_edge(x,y,val);
add_edge(y,x,val);
}
s=26;
dijkstra();
ll tmp=inf,g;
for(int i=1;i<=25;i++)
{
if(tmp>dist[i])
{
tmp=dist[i];
g=i;
}
}
cout<<char(g-1+'A')<<" "<<tmp<<endl;
return 0;
}
相关文章
- Home Server
- MacOS安装Eclipse后启动报错:The JVM shared library "/Library/Internet Plug-Ins/JavaAppletPlugin.plugin/Contents/Home/bin/../lib/server/libjvm.dylib" does not contain the JNI_CreateJavaVM symbol.
- [Angular2 Router] Configuring a Home Route and Fallback Route - Learn An Essential Routing Concept
- SAP Spartacus的home page navigation逻辑
- Hybris Commerce Cloud backoffice的一些使用截图 - home工作中心
- Atitit r2017 ra doc list on home ntpc.docx
- SAP Fiori Launchpad shell.handleGoHome() - home按钮的实现
- SAP Spartacus b2b home页面的自动换行是怎么做到的
- Error launching Studio If you already have a 64-bit JDK installed, define a JAVA_HOME variable in Co
- android Home Launcher3解析