1 条题解
-
0
C++ :
#include <iostream> #include <cstdio> #include <cstring> #define foru(i, l, r) for (int i = l; i <= r; i ++) using namespace std; const int N = 510; int m, n, e[N][N], a[N]; bool vst[N]; void dijkstra() { vst[1] = true; foru (i, 2, n) { int t = 0; foru (j, 1, n) { if (!vst[j] && e[1][j] < e[1][t]) t = j; } vst[t] = true; foru (j, 1, n) { if (!vst[j]) e[1][j] = min(e[1][j], e[1][t]+e[t][j]); } } } int main() { scanf("%d%d\n", &m, &n); memset(e, 0x3f, sizeof(e)); while (m--) { int num = 0, cnt = 0; char ch; while (scanf("%c", &ch)) { if (ch>='0' && ch<='9') { num = num*10 + ch-'0'; } else { a[++cnt] = num; num = 0; if (ch == '\n') break; } } foru (i, 1, cnt) { foru (j, i+1, cnt) { e[a[i]][a[j]] = 1; } } } dijkstra(); if (e[1][n] == 0x3f3f3f3f) cout << "NO"; else cout << e[1][n] - 1; return 0; }
Pascal :
const maxn=500; var a:array[1..maxn,1..maxn]of integer; b:array[1..maxn]of boolean; t:array[1..maxn]of longint; x,y,i,j,max,k,m,n:integer; begin readln(m,n); fillchar(a,sizeof(a),0); y:=0; for i:=1 to m do begin fillchar(t,sizeof(t),0); while not eoln do begin inc(y); read(t[y]); end; readln; for j:=1 to y-1 do for k:=j+1 to y do a[t[j],t[k]]:=1; end; fillchar(b,sizeof(b),false); b[1]:=true; for i:=2 to n do begin max:=maxint; for j:=1 to n do if(not b[j])and(a[1,j]<>0)and(a[1,j]<max)then begin max:=a[1,j]; x:=j; end; b[x]:=true; for j:=2 to n do if(a[1,x]<>0)and(a[x,j]<>0)then if(a[1,j]=0)or(a[1,j]>a[1,x]+a[x,j])then a[1,j]:=a[1,x]+a[x,j]; end; if a[1,n]-1=-1 then write('NO') else write(a[1,n]-1); end.
- 1
信息
- ID
- 370
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者