POJ 1511 Invitation Cards

Dear 丶 2022-05-06 16:27 144阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：有向图，求从起点1到每个点的最短路然后再回到起点1的最短路之和。（保证有解）   分析：开始用SPFA+vectorTLE了，改成前向星就过了。图上没有负环最好还是用堆优化后的dijkstra。 ##

## AC代码（前向星）： ##

#pragma comment(linker, "/STACK:102400000,102400000")
    ///#include<unordered_map>
    ///#include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int n,p,q,h1[N],h2[N],tot,d[N],ct[N],vs[N];
    ll ans=0;
    
    struct eg{
        int to,w,nt;
    };
    eg e1[N],e2[N];
    
    void init() {
        mst(h1,-1);
        mst(h2,-1);
        tot=0;
        ans=0;
    }
    
    void add(eg *tpeg,int *tphd,int u,int v,int w) {
        tpeg[tot].to=v;
        tpeg[tot].w=w;
        tpeg[tot].nt=tphd[u];
        tphd[u]=tot;
    }
    
    void spfa(eg *e,int *hd) {
        mst(d,inf);
        d[1]=0;
        mst(vs,0);
        mst(ct,0);
        queue<int> que;
        que.push(1);
        while(!que.empty()) {
            int tp=que.front(); que.pop();
            vs[tp]=0;
            for(int i=hd[tp];~i;i=e[i].nt) {
                int vv=e[i].to,ww=e[i].w;
                if(d[tp]+ww<d[vv]) {
                    d[vv]=d[tp]+ww;
                    if(!vs[vv]) que.push(vv),vs[vv]=1;
                }
            }
        }
        for(int i=1;i<=p;i++) ans+=d[i];
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        ///cin>>n;
        scanf("%d",&n);
        while(n--) {
            init();
            ///cin>>p>>q;
            scanf("%d%d",&p,&q);
            for(int i=1;i<=q;i++) {
                int u,v,w;
                ///cin>>u>>v>>w;
                scanf("%d%d%d",&u,&v,&w);
                add(e1,h1,u,v,w);
                add(e2,h2,v,u,w);
                tot++;
            }
            spfa(e1,h1);
            spfa(e2,h2);
            ///cout<<ans<<endl;
            printf("%lld\n",ans);
        }
        return 0;
    }

## TLE的代码（vector）： ##

#pragma comment(linker, "/STACK:102400000,102400000")
    ///#include<unordered_map>
    ///#include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int n,p,q,h1[N],h2[N],tot,d[N],ct[N],vs[N];
    ll ans=0;
    
    struct eg{
        int to,w;
    };
    vector<eg> e1[N],e2[N];
    
    void init() {
        for(int i=1;i<=p;i++) e1[i].clear(),e2[i].clear();
        ans=0;
    }
    
    void spfa(vector<eg> e[N]) {
        mst(d,inf);
        d[1]=0;
        mst(vs,0);
        ///mst(ct,0);
        queue<int> que;
        que.push(1);
        while(!que.empty()) {
            int tp=que.front(); que.pop();
            vs[tp]=0;
            for(int i=0;i<e[tp].size();i++) {
                eg vv=e[tp][i];
                if(d[tp]+vv.w<d[vv.to]) {
                    d[vv.to]=d[tp]+vv.w;
                    if(!vs[vv.to]) que.push(vv.to),vs[vv.to]=1;
                }
            }
        }
        for(int i=1;i<=p;i++) ans+=d[i];
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        scanf("%d",&n);
        while(n--) {
            init();
            scanf("%d%d",&p,&q);
            for(int i=1;i<=q;i++) {
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                e1[u].pb({v,w});
                e2[v].pb({u,w});
            }
            spfa(e1);
            spfa(e2);
            printf("%lld\n",ans);
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1511