1 条题解
-
0
C :
#include <stdio.h> int main() { char E[501][501]={0},chr,p[501]={0}; int V[501],N,i,j,l,m,t[500]={0}; scanf("%d%d",&i,&N); while (scanf("%c",&chr)!=EOF) { if (chr=='\n') l=1; if (scanf("%d",&m)==EOF) break; for (i=1;i<l;i++) E[t[i]][m]=1; t[l++]=m; } for (i=2;i<=N;i++) V[i]=1<<26; V[1]=0; for (i=0;i<N;i++) { for (m=1;p[m];m++); for (j=m+1;j<=N;j++) if (p[j]==0&&V[m]>V[j]) m=j; p[m]=1; for (j=1;j<=N;j++) if (p[j]==0&&E[m][j]&&V[m]+1<V[j]) V[j]=V[m]+1; } if (V[N]==1<<26) printf("NO"); else printf("%d",V[N]==0?0:V[N]-1); return 0; }
C++ :
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int a[501][501]={0},dis[501]; int m,n; void init(); void spfa(int); int main() { //freopen("Travel5.in","r",stdin); init(); spfa(1); if(dis[n]==0x7f7f7f7f)cout<<"NO"<<endl; else cout<<dis[n]-1<<endl; return 0; } void init() { cin>>m>>n; getchar(); for(int i=1;i<=m;i++) { int temp[501],len=0,lens=0,x; string s; getline(cin,s); while(lens<s.size()) { while(s[lens]==' ') lens++; x=0; while(s[lens]>='0' && s[lens]<='9') { x=10*x+s[lens]-48; lens++; } temp[++len]=x; //cout<<x<<' '; } //cout<<endl; /*char ch=1; while(ch!=10)//10是换行的asscall值 { cin>>temp[++len]; ch=getchar(); } */ for(int j=1;j<len;j++) for(int k=j+1;k<=len;k++)a[temp[j]][temp[k]]=1; } } void spfa(int x) { queue<int> q; bool flag[501]={0}; memset(dis,0x7f,sizeof(dis)); q.push(x); flag[x]=true; dis[x]=0; while(!q.empty()) { int k=q.front(); for(int i=1;i<=n;i++) { if(a[k][i]>0 && dis[i]>a[k][i]+dis[k]) { dis[i]=dis[k]+a[k][i]; if(!flag[i]) { q.push(i); flag[i]=true; } } } flag[k]=false; q.pop(); } }
Pascal :
program travel; type list=record x,z,n:longint; end; var k:array[0..500]of longint; f:array[0..1000000]of longint; e:array[1..100000]of list; d:array[0..500]of longint; v:array[0..500]of boolean; min,n,m,o:longint; procedure add(a,b,c:longint); begin inc(o); e[o].x:=b; e[o].z:=c; e[o].n:=k[a]; k[a]:=o; end; procedure init; var i,j,k,l:longint; a:array[1..100]of longint; begin readln(m,n); for l:=1 to m do begin k:=0; while not eoln do begin inc(k); read(a[k]); end; readln; for i:=1 to k-1 do for j:=i+1 to k do if i<>j then add(a[i],a[j],1); end; end; procedure spfa; var head,tail,now,t:longint; begin f[1]:=1; head:=0; tail:=1; v[1]:=true; fillchar(d,sizeof(d),127); d[1]:=0; while head<tail do begin inc(head); now:=f[head]; v[now]:=false; t:=k[now]; while t<>0 do begin if d[now]+e[t].z<d[e[t].x] then begin d[e[t].x]:=d[now]+e[t].z; if not v[e[t].x] then begin v[e[t].x]:=true; inc(tail); f[tail]:=e[t].x; end; end; t:=e[t].n; end; end; if d[n]=2139062143 then writeln('NO') else writeln(d[n]-1); end; begin while not eof do begin init; if (m=0)and(n=0) then begin close(input);close(output);halt;end; spfa; end; close(input);close(output); end.
- 1
信息
- ID
- 948
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者