Pizza Delivery

C++(clang++ 11.0.1) 解法, 执行用时: 151ms, 内存消耗: 29112K, 提交时间: 2022-10-23 14:56:12

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
typedef pair<long long,int> pa;
const int MAXN=1e5+5;
bool mindis[MAXN],bridge[MAXN],better[MAXN];
int n,m;
struct Graph
{
    vector<pii>G[MAXN];
    vector<int>g[MAXN],point;
    long long dis[MAXN],dp[MAXN];
    int ins[MAXN];
    bool vis[MAXN];
    void add(int x,int y,int z){G[x].push_back({y,z});}
    void dijkstra(int s)
    {
        priority_queue< pa,vector<pa>,greater<pa> >q;
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[s]=0,q.push({dis[s],s});
        while(!q.empty())
        {
            int x=q.top().second;q.pop();
            if(vis[x]) continue;
            vis[x]=1;
            for(auto [y,z]:G[x]) if(dis[y]>dis[x]+z) dis[y]=dis[x]+z,q.push({dis[y],y});
        }
    }
    void toposort()
    {
        queue<int>q;
        for(int i=1;i<=n;++i) if(!ins[i]) q.push(i);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            point.push_back(x);
            for(auto y:g[x]) if(--ins[y]==0) q.push(y);
        }
    }

}G1,G2;
struct EDGE
{
    int u,v,w;
}edge[MAXN];
int main()
{
    cin>>n>>m;
    int u,v,w;
    for(int i=1;i<=m;++i) scanf("%d %d %d",&u,&v,&w),G1.add(u,v,w),G2.add(v,u,w),edge[i]=(EDGE){u,v,w};
    G1.dijkstra(1),G2.dijkstra(2);
    for(int i=1;i<=m;++i)
    {
        u=edge[i].u,v=edge[i].v,w=edge[i].w;
        if(G1.dis[u]+G2.dis[v]+w==G1.dis[2])
        {
            mindis[i]=1;
            G1.g[u].push_back(v),++G1.ins[v];
            G2.g[v].push_back(u),++G2.ins[u];
        }
    }
    G1.toposort(),G1.dp[1]=1;
    for(auto x:G1.point) for(auto y:G1.g[x]) G1.dp[y]+=G1.dp[x];
    G2.toposort(),G2.dp[2]=1;
    for(auto x:G2.point) for(auto y:G2.g[x]) G2.dp[y]+=G2.dp[x];
    for(int i=1;i<=m;++i)
    {
        u=edge[i].u,v=edge[i].v,w=edge[i].w;
        if(mindis[i] && G1.dp[u]*G2.dp[v]==G1.dp[2]) bridge[i]=1;
        else if(!mindis[i] && G1.dis[v]+G2.dis[u]+w<G1.dis[2]) better[i]=1;
    }
    for(int i=1;i<=m;++i)
    {
        if(bridge[i]) printf("SAD\n");
        else if(better[i]) printf("HAPPY\n");
        else printf("SOSO\n");
    }
    return 0;
}
/*
4 5
1 3 5
3 4 6
4 2 7
2 1 18
2 3 12
*/

C++(g++ 7.5.0) 解法, 执行用时: 93ms, 内存消耗: 22364K, 提交时间: 2022-10-06 13:24:37

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const int N=1e5+10;
LL n,m,ans;
LL d1[N],d2[N],x[N],y[N],z[N];

LL cnt=1,head[N],to[N<<1],nxt[N<<1],len[N<<1];
void add_edge(LL x,LL y,LL z) {
    nxt[++cnt]=head[x]; to[cnt]=y; len[cnt]=z; head[x]=cnt;
}

bool vis[N]; 
priority_queue<pii> q;
void Dijkstra(LL d[],LL s) {
    while (!q.empty()) q.pop();
    memset(vis,0,sizeof(vis));
    d[s]=0; q.push(make_pair(0,s));
    while (!q.empty()) {
        pii x=q.top(); q.pop();
        if (vis[x.second]) continue;
        vis[x.second]=1;
        for (LL i=head[x.second];i;i=nxt[i]) {
            LL y=to[i];
            if (d[y]>d[x.second]+len[i]) {
                d[y]=d[x.second]+len[i];
                q.push(make_pair(-d[y],y));
            }
        }
    }
}

int num,low[N],dfn[N],bridge[N];
void tarjan(int x,int in) {
    dfn[x]=low[x]=++num;
    for (int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if (!dfn[y]) {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            
            if (low[y]>dfn[x])
                bridge[len[i]]=bridge[len[i^1]]=1;
        } else if (i!=(in^1))
            low[x]=min(low[x],dfn[y]);
    }
}

void getbridge() {
    cnt=1; memset(head,0,sizeof(head));
    for (int i=1;i<=m;i++)
        if (d1[x[i]]+z[i]+d2[y[i]]==ans) 
            add_edge(x[i],y[i],i),add_edge(y[i],x[i],i);
    for (int i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i,0);    
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
    
    memset(d1,0x3f,sizeof(d1)); memset(d2,0x3f,sizeof(d2));
    for (int i=1;i<=m;i++) add_edge(x[i],y[i],z[i]);
    Dijkstra(d1,1);
    
    cnt=1; memset(head,0,sizeof(head));
    for (int i=1;i<=m;i++) add_edge(y[i],x[i],z[i]);
    Dijkstra(d2,2);
    
    ans=d1[2]; getbridge();
    
    for (int i=1;i<=m;i++)
        if (ans>d1[y[i]]+d2[x[i]]+z[i]) puts("HAPPY");
        else if (bridge[i]) puts("SAD"); else puts("SOSO");
    return 0;
}

详情