单源最短路的扩展应用

选择最佳线路

有一天，琪琪想乘坐公交车去拜访她的一位朋友。

由于琪琪非常容易晕车，所以她想尽快到达朋友家。

现在给定你一张城市交通路线图，上面包含城市的公交站台以及公交线路的具体分布。

已知城市中共包含 n 个车站（编号1~n）以及 m 条公交线路。

每条公交线路都是 单向的，从一个车站出发直接到达另一个车站，两个车站之间可能存在多条公交线路。

琪琪的朋友住在 s 号车站附近。

琪琪可以在任何车站选择换乘其它公共汽车。

请找出琪琪到达她的朋友家（附近的公交车站）需要花费的最少时间（最短路）。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含三个整数 n,m,s，分别表示车站数量，公交线路数量以及朋友家附近车站的编号。

接下来 m 行，每行包含三个整数 p,q,，表示存在一条线路从车站 p 到达车站 q，用时为 t。

接下来一行，包含一个整数 w，表示琪琪家附近共有 w 个车站，她可以在这 w 个车站中选择一个车站作为始发站。

再一行，包含 w 个整数，表示琪琪家附近的 w 个车站的编号。

输出格式

每个测试数据输出一个整数作为结果，表示所需花费的最少时间。

如果无法达到朋友家的车站，则输出 -1。

每个结果占一行。

数据范围

n≤1000,m≤20000
1≤s≤n
0<w<n
0<t≤1000

输入样例：

输出样例：

1
-1

特点：多起点有唯一终点的最短路径

思路：可以反向建图把终点当成起点起点当成终点找一个最短的路径

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=1010,M=2e4+10,INF=0x3f3f3f3f;
int h[N],ne[M],e[M],w[M],idx;
int dist[N];
bool st[N];
int n,m,s;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void spfa(int s)
{
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    queue<int>q;
    q.push(s);
    st[s]=1;
    dist[s]=0;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=-1)
    {
        memset(h,-1,sizeof h);
        idx=0;
        while(m--)
        {
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
            add(b,a,c);
        }
        int x;scanf("%d",&x);
        int a[N]={0};
        for(int i=1;i<=x;i++) scanf("%d",&a[i]);
        spfa(s);
        int min1=INF;
        for(int i=1;i<=x;i++)
        {
            int y=a[i];
            if(dist[y]<min1) min1=dist[y];
        }
       if(min1==INF) cout<<"-1"<<endl;
       else cout<<min1<<endl;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
//M太小了 因为多加了 虚拟原点到原点的边
const int N=1010,M=3e4+10,INF=0x3f3f3f3f;
int h[N],ne[M],e[M],w[M],idx;
int dist[N];
bool st[N];
int n,m,s;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void spfa()
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    queue<int>q;
    q.push(0);
    dist[0]=0;
    st[0]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=1;
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=-1)
    {
        memset(h,-1,sizeof h);
        idx=0;
        while(m--)
        {
            int a,b,c;scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        int x;scanf("%d",&x);
        while(x--)
        {
            int num;scanf("%d",&num);
            add(0,num,0);
        }
        spfa();
        if(dist[s]==INF) cout<<"-1"<<endl;
        else cout<<dist[s]<<endl;
    }
}

拯救大兵瑞恩

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。

瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。

迷宫的外形是一个长方形，其南北方向被划分为 N 行，东西方向被划分为 M 列，于是整个迷宫被划分为 N×M 个单元。

每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。

南北或东西方向相邻的 2 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。

注意： 门可以从两个方向穿过，即可以看成一条无向边。

迷宫中有一些单元存放着钥匙，同一个单元可能存放 多把钥匙，并且所有的门被分成 PP 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 (N,M) 单元里，并已经昏迷。

迷宫只有一个入口，在西北角。

也就是说，麦克可以直接进入 (1,1) 单元。

另外，麦克从一个单元移动到另一个相邻单元的时间为 1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入格式

第一行有三个整数,分别表示 N,M,P 的值。

第二行是一个整数 k，表示迷宫中门和墙的总数。

接下来 k 行，每行包含五个整数，Xi1,Yi1,Xi2,Yi2,Gi 当 Gi≥1时，表示 (Xi1,Yi1)单元与 (Xi2,Yi2) 单元之间有一扇第 Gi 类的门，当 Gi=0 时，表示 (Xi1,Yi1) 单元与 (Xi2,Yi2) 单元之间有一面不可逾越的墙。

接下来一行，包含一个整数 S，表示迷宫中存放的钥匙的总数。

接下来 S 行，每行包含三个整数 Xi1,Yi1,Qi 表示 (Xi1,Yi1)单元里存在一个能开启第 Qi 类门的钥匙。

输出格式

输出麦克营救到大兵瑞恩的最短时间。

如果问题无解，则输出 -1。

数据范围

|Xi1−Xi2|+|Yi1−Yi2|=1
0≤Gi≤P
1≤Qi≤P
1≤N,M,P≤10
1≤k≤150

输入样例：

输出样例：

样例解释：

迷宫如下所示：

有向图的拓扑序列

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y) x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围

1≤n,m≤10^5

输入样例：

输出样例：

1 2 3

一个有向无环图至少存在一个入度为0的点

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int h[N],e[N],ne[N],idx;
int q[N];
int d[N];//入度
int n,m;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool topsort()
{
    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
     if(!d[i]) 
     q[tt++]=i;//将入度为零的点入队
    while(hh<tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            d[j]--;//删除点t指向点j的边
            if(d[j]==0)//如果点j的入度为零了,就将点j入队
            q[tt++]=j;
        }
    }
    return tt==n;
    //表示如果n个点都入队了话,那么该图为拓扑图,返回true,否则返回false
}
int dist[N];
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    if(topsort())
    {
        for(int i=0;i<n;i++) cout<<q[i]<<" ";
    }
    else cout<<"-1"<<endl;
    return 0;
}