首页 > 代码库 > VIJOS-P1635 城市连接
VIJOS-P1635 城市连接
嘿嘿嘿,逆向spfa,貌似不难...
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <iostream> #include <queue> using namespace std; #define N 1005 int n; int map[N][N]; struct node { int next,to,val; int next1,from; }e[N*N]; int head[N],tail[N],cnt,vis[N],dis[N],a[N]; void add(int x,int y,int z) { e[++cnt].next=head[x]; e[cnt].to=y; e[cnt].val=z; head[x]=cnt; e[cnt].next1=tail[y]; e[cnt].from=x; tail[y]=cnt; return ; } int dijkstra(int start) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[start]=0; for(int i=1;i<=n;i++) { int x; int min_value=http://www.mamicode.com/0x3f3f3f; for(int j=1;j<=n;j++) { if(vis[j]!=1&&dis[j]<min_value) { min_value=dis[j]; x=j; } } vis[x]=1; for(int k=head[x];k!=-1;k=e[k].next) { int ans=e[k].to; if(vis[ans]!=1) { if(dis[ans]>dis[x]+e[k].val) { dis[ans]=dis[x]+e[k].val; } } } } return dis[n]; } void spfa(int start) { memset(vis,0,sizeof(vis)); queue <int>q; q.push(start); vis[start]=1; int num=1; a[num]=n; while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=tail[x];i!=-1;i=e[i].next1) { if(dis[e[i].from]==dis[x]-e[i].val) { a[++num]=e[i].from; q.push(e[i].from); } } } return ; } int main() { scanf("%d",&n); memset(head,-1,sizeof(head)); memset(tail,-1,sizeof(tail)); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&map[i][j]); if(map[i][j]!=0) { add(i,j,map[i][j]); } } } int ans=dijkstra(1); spfa(n); int i; for(i=1;;i++) { if(a[i+1]==0)break; } for(;i>=1;i--) { printf("%d ",a[i]); } puts(""); printf("%d\n",ans); }
VIJOS-P1635 城市连接
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。