首页 > 代码库 > HDU 2923 Einbahnstrasse
HDU 2923 Einbahnstrasse
英语渣就是这点不好。。。
巨恶心这种描述多的题。。
大意就是求 从一个点出发,到某些点,然后又从那些点返回的距离之和的 最小值。
Dijkstra+邻接矩阵。 正向建图,求出出发距离,然后swap边,求出 返回距离。
注意的是 车可能有重复的。某个点有多少车就需要乘以车的数量。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m; int g[101][101]; map<string,int>str; int d[101]; void Dijkstra(int start,int *dis) { bool vis[101]; for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=0; vis[start]=1,dis[start]=0; for(int i=1;i<n;i++) { int mi=INF,k=start; for(int j=1;j<=n;j++) if(dis[j]<mi&&!vis[j])mi=dis[j],k=j; vis[k]=1; for(int j=1;j<=n;j++) { if(!vis[j]&&dis[j]>dis[k]+g[k][j]&&g[k][j]<INF) dis[j]=dis[k]+g[k][j]; } } } int main() { int cot=1,top; while(scanf("%d%d%d",&n,&top,&m),n||top||m) { str.clear(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=INF; int dis1[101],dis2[101]; int car[101]; memset(car,0,sizeof(car)); string a,b,c; int start,num=1; cin>>a; if(str[a]==0)str[a]=num++; start=str[a]; int carnum=0; for(int i=0;i<top;i++) { cin>>a; if(str[a]==0)str[a]=num++,d[carnum++]=str[a]; car[str[a]]++; } int u,v,t; while(m--) { cin>>a>>b>>c; if(str[a]==0)str[a]=num++; u=str[a]; if(str[c]==0)str[c]=num++; v=str[c]; int sum=0; int k=0; while(b[k]=='-'||b[k]=='<')k++; while(b[k]!='-')sum=sum*10+b[k]-'0',k++; t=sum; if(b[0]=='<')g[v][u]=min(g[v][u],t); if(b[b.length()-1]=='>')g[u][v]=min(g[u][v],t); } Dijkstra(start,dis1); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) swap(g[i][j],g[j][i]); Dijkstra(start,dis2); int ans=0; for(int i=0;i<carnum;i++) { int v=d[i]; ans+=(dis1[v]+dis2[v])*car[v]; } printf("%d. %d\n",cot++,ans); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。