POJ 3463 - Sightseeing

题意:告诉你那n个点以及m条单向边。询问你从s点到e点最短路和比最短路长度大一的路一共有多少条。

思路:dijkstra变形。分别从起点和终点求一边dijkstra。用cnt数组分别记录从起点到达第i个点且长度为最短长度的路径数以及从原点到达第i个点且长度为最短长度的路径数。_cnt数组记录到第i个节点的距离为最短距离+1的路径数。注意_cnt[i]所记录的路径只包括第i个节点的pre节点为最短路而pre节点到第i个节点不是最短路的情况。这样可以防止重复计算。

具体的松弛操作:设u为未经过的节点中距离原点最近的点,那么枚举u的每一条边,如果dist[flag][u]+e.w==dist[flag][e.v]

那么到达v点且为最短路的路径数cnt[v]+=cnt[u]。如果dist[u]+e.w==dist[e.v]+1,那么到达v点且长度为最短路+1的路径数_cnt[v]+=cnt[u]。如果如果dist[u]+e.w<dist[e.v],先判断dist[flag][u]+e.w等不等于dist[e.v]+1,如果等于,那么原来的最短路路径数就变成了最短路长度加1的路径数_cnt[v]=cnt[v],如果不等于,那么最短路长度加1的路径数就为0。接着更新dist[v]并且让cnt[v]=cnt[u]。接着在dijkstra求出从终点到第i个点的最短路径数就好了,这一次dijkstra不需要再求最短路径+1的条数了。

然后最终的答案就等于cnt[e]再加上从起点到第i个点长度为最短路长度+1乘上终点到第i个点的最短路的路径数。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXM=11000;
const int MAXN=1100;
struct Edge{
    int v,w,nex;
}edge[2][MAXM];
int head[2][MAXN];
bool vis[MAXN];
int dist[2][MAXN];
int tot1,tot2,n,m,s,e,u,v,w;
int cnt[2][MAXN];
int _cnt[MAXN];
void addedge(int u,int v,int w)
{
    edge[0][tot1].v=v;
    edge[0][tot1].w=w;
    edge[0][tot1].nex=head[0][u];
    head[0][u]=tot1++;

    edge[1][tot2].v=u;
    edge[1][tot2].w=w;
    edge[1][tot2].nex=head[1][v];
    head[1][v]=tot2++;
}

void dijkstra(int flag)
{
    int ss=flag?e:s;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        dist[flag][i]=INF;
    cnt[flag][ss]=1;
    dist[flag][ss]=0;
    while(1)
    {
        int u=-1;
        for(int v=1;v<=n;v++)
            if(!vis[v]&&(u==-1||dist[flag][v]<dist[flag][u]))
                u=v;
        if(u==-1)
            break;
        vis[u]=true;
        for(int i=head[flag][u];i!=-1;i=edge[flag][i].nex)
        {
            Edge e=edge[flag][i];
            if(dist[flag][u]+e.w==dist[flag][e.v])
                cnt[flag][e.v]+=cnt[flag][u];
            if(dist[flag][u]+e.w==dist[flag][e.v]+1&&!flag)
                _cnt[e.v]+=cnt[flag][u];
            if(dist[flag][u]+e.w<dist[flag][e.v])
            {
                if(!flag)
                {
                    if(dist[flag][u]+e.w+1==dist[flag][e.v])
                        _cnt[e.v]=cnt[flag][e.v];
                    else
                        _cnt[e.v]=0;
                }
                dist[flag][e.v]=dist[flag][u]+e.w;
                cnt[flag][e.v]=cnt[flag][u];
            }
        }
    }
}

void init()
{
    tot1=tot2=0;
    memset(head,-1,sizeof(head));
    memset(cnt,0,sizeof(cnt));
    memset(_cnt,0,sizeof(cnt));
}
int main()
{
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%d",&n,&m);
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        scanf("%d%d",&s,&e);
        dijkstra(0);
        dijkstra(1);
        int ans=cnt[0][e];
        //printf("%d\n",ans);
        //for(int i=1;i<=n;i++)
            //printf("%d %d\n",_cnt[i],cnt[1][i]);
        for(int i=1;i<=n;i++)
            if(dist[0][i]+dist[1][i]==dist[0][e])
                ans+=_cnt[i]*cnt[1][i];
        printf("%d\n",ans);
    }
    return 0;
}

时间: 08-30

POJ 3463 - Sightseeing的相关文章

poj 3463 Sightseeing(最短路+次短路)

http://poj.org/problem?id=3463 大致题意:给出一个有向图,从起点到终点求出最短路和次短路的条数之和. 解法: 用到的数组:dis[i][0]:i到起点的最短路,dis[i][1]:i到起点的严格次短路 vis[i][0],vis[i][1]:同一维的vis数组,标记距离是否已确定 sum[i][0]:i到起点的最短路条数,sum[i][1]:i到起点的次短路条数 同一维dijkstra,内循环先找出最短的距离(次短路或最短路)d,然后枚举与该点相连的点: if(d

poj 3463 Sightseeing(次短路+条数统计)

/* 对dij的再一次理解 每个点依旧永久标记 只不过这里多搞一维 0 1 表示最短路还是次短路 然后更新次数相当于原来的两倍 更新的时候搞一下就好了 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #define maxn 1010 using namespace std; int T,n,m,num,head[m

POJ 1637 Sightseeing tour(混合图的欧拉回路)

题目链接 建个图,套个模板. #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <algorithm> #include <vector> #include <string> #include <queue> using namespace std; #define INF 0x3ffffff str

POJ 1734 Sightseeing trip (Floyd 最小环+记录路径)

Sightseeing trip Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5040   Accepted: 1932   Special Judge Description There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attra

POJ 3621 Sightseeing Cows(最优比例环+SPFA检测)

Sightseeing Cows Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10306   Accepted: 3519 Description Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to

【图论补完计划】poj 3463 (次短路计数 dijkstra)

Sightseeing Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 9127   Accepted: 3206 Description Tour operator Your Personal Holiday organises guided bus trips across the Benelux. Every day the bus moves from one city S to another city F. O

POJ 1637 Sightseeing tour (混合图欧拉回路)

Sightseeing tour Description The city executive board in Lund wants to construct a sightseeing tour by bus in Lund, so that tourists can see every corner of the beautiful city. They want to construct the tour so that every street in the city is visit

poj 3463 最短路与次短路的方案数求解

Sightseeing Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8968   Accepted: 3139 Description Tour operator Your Personal Holiday organises guided bus trips across the Benelux. Every day the bus moves from one city S to another city F. O

poj 1734 Sightseeing trip判断最短长度的环

Sightseeing trip Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 5590   Accepted: 2151   Special Judge Description There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attra