| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 20274 | Accepted: 7553 |
Description
Input
Output
Sample Input
3 2 1 2 2 3 2 3 1 2 1 2
Sample Output
0
Dijkstra+堆优化，比较简单的一道题。
说一下思路吧：
每个节点与所有可到达节点之间连边，与初始指向节点的权值为0，与其余可到达的节点的权值为1。
然后求最短路。
#include <cstdio>
#include <queue>
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while (c<‘0‘ || c>‘9‘){if (c==‘-‘)f=-1;c=getchar();}
while (c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}
inline void print(int x)
{
if (x<0)x=-x,putchar(‘-‘);
if (x>9)print(x/10);
putchar(x%10+48);
}
inline void print(int x,char c)
{
print(x);
putchar(c);
}
const int INF=10000000;
const int MAXN=101;
int n,from,to;
int a[MAXN];
int cost[MAXN][MAXN];
struct dij
{
int id,dis;
bool operator < (const dij tmp) const
{
return dis>tmp.dis;
}
};
int dis[MAXN];
inline void dijkstra()
{
int u;
for (int i=1;i<=n;i++)dis[i]=INF;
dis[from]=0;
priority_queue<dij> Q;
Q.push((dij){from,0});
while (!Q.empty())
{
u=Q.top().id;Q.pop();
for (int i=1;i<=n;i++)
if (dis[u]+cost[u][i]<dis[i])
{
dis[i]=dis[u]+cost[u][i];
Q.push((dij){i,dis[i]});
}
}
}
int main()
{
n=read();from=read();to=read();
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cost[i][j]=INF;
for (int i=1;i<=n;i++)cost[i][i]=0;
int top,k;
for (int i=1;i<=n;i++)
{
top=read();
if (!top)continue;
cost[i][read()]=0;
for (int j=2;j<=top;j++)cost[i][read()]=1;
}
dijkstra();
if (dis[to]<INF)print(dis[to],‘\n‘);
else print(-1,‘\n‘);
return 0;
}
原文：https://www.cnblogs.com/lzxzy-blog/p/10501833.html