BZOJ-1375 Bicriterial routing 双调路径(SPFA)

传送门

思路：设二维数组dp[i][j]表示在第i个城市已经花费j元的最小时间。跑一遍BFS-SPFA即可。

很明显当前不是最佳的情况下不用继续迭代，所以这题还可以用树状数组优化，但是懒得写了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int n,m,st,ed,maxc;
int dp[105][10005];
const int MAXN=105;
const int INF=0x3f3f3f3f;
struct edge
{
    int v;
    int cost;
    int time;
    edge(int _v=0,int _cost=0,int _time=0):v(_v),cost(_cost),time(_time) {}
};
vector<edge>g[MAXN];
void addedge(int u,int v,int w,int t)
{
    g[u].push_back(edge(v,w,t));
}
struct node{
int p,c;
};
bool vis[MAXN][9905];
void SPFA()
{
    queue<node>que;
    while(!que.empty())que.pop();
    for(int i=1; i<=n; i++)
    {
        for (int j=0;j<=maxc;j++)
        {
            dp[i][j]=INF;
            vis[i][j]=0;
        }
    }
    que.push((node){st,0});
    dp[st][0]=0;
    vis[st][0]=true;
    while(!que.empty())
    {
        node r=que.front();
        que.pop();
        int p=r.p;
        int c=r.c;
        vis[p][c]=false;
        for(int i=0; i<g[p].size(); i++)
        {
            int v=g[p][i].v;
            int cc=g[p][i].cost+c;
            if (cc>maxc)
                continue;
            if(dp[v][cc]>dp[p][c]+g[p][i].time)
            {
                dp[v][cc]=dp[p][c]+g[p][i].time;
                if(!vis[v][cc])
                {
                    vis[v][cc]=true;
                    que.push((node){v,cc});
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    maxc=(n-1)*100;
    for (int i=1;i<=n;i++)
        g[i].clear();
    for (int i=0;i<m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        addedge(a,b,c,d);
        addedge(b,a,c,d);
    }
    SPFA();
    int ans=0,minn=maxc+1;
    for (int i=0;i<=maxc;i++)
    {
        if (dp[ed][i]==INF||dp[ed][i]>=minn)
            continue;
        minn=dp[ed][i];
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}