- 技术博客
- PAT甲 2019年秋季考试7-4 Dijkstra Sequence
#include<cstdio>
#include<vector>
#include<unordered_set>
#include<cstring>
using namespace std
;
const int maxn
= 1e3+10, INF
= 1e9;
int dis
[maxn
][maxn
], d
[maxn
];
bool vis
[maxn
];
int Nv
, Ne
;
vector
<int> link
[maxn
], a
;
void Dijkstra()
{
fill(d
+1, d
+1+Nv
, INF
);
d
[a
[0]] = 0;
int index
= -1;
unordered_set
<int> temp
;
for(int i
= 1; i
<= Nv
; i
++)
{
int u
= -1, Min
= INF
;
for(int j
= 1; j
<= Nv
; j
++)
{
if(d
[j
] < Min
&& vis
[j
] == false)
{
Min
= d
[j
];
temp
.clear();
temp
.insert(j
);
}
else if(d
[j
] == Min
&& vis
[j
] == false)
temp
.insert(j
);
}
if(temp
.find(a
[++index
]) != temp
.end())
{
u
= a
[index
];
temp
.clear();
}
else
{
printf("No\n");
return;
}
vis
[u
] = true;
for(int k
= 0; k
< link
[u
].size(); k
++)
{
int x
= link
[u
][k
];
if(vis
[x
] == false && dis
[u
][x
] != 0)
{
if(d
[u
] + dis
[u
][x
] < d
[x
])
d
[x
] = d
[u
] + dis
[u
][x
];
}
}
}
printf("Yes\n");
}
int main()
{
scanf("%d%d", &Nv
, &Ne
);
for(int i
= 1; i
<= Ne
; i
++)
{
int a
, b
, distance
;
scanf("%d%d%d", &a
, &b
, &distance
);
dis
[a
][b
] = dis
[b
][a
] = distance
;
link
[a
].push_back(b
), link
[b
].push_back(a
);
}
int k
, num
;
scanf("%d", &k
);
for(int i
= 1; i
<= k
; i
++)
{
a
.clear();
for(int j
= 1; j
<= Nv
; j
++)
{
scanf("%d", &num
);
a
.push_back(num
);
}
memset(vis
, 0, sizeof(vis
));
Dijkstra();
}
}
