zoj 2008 Invitation Cards

zoj 2008 Invitation Cards

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <vector>#include <queue>#define INF 1010000000using namespace std;const int maxn = 1001000;struct node{    int id,w;    node(){}    node(int _id,int _w){        id = _id;   w = _w;    }    bool operator<(const node &p)const{         return w > p.w; // basic coding    }};vector<node>V[maxn];int n,m;int x[maxn],y[maxn],z[maxn],dis[maxn];bool vis[maxn];int spfa(){    int i;    int T;    queue<int>Q;    memset(vis,0,sizeof(vis));    memset(dis,0x3f,sizeof(dis));    dis[1] = 0;    vis[1] = 1;    Q.push(1);    while(!Q.empty()){         T = Q.front();   Q.pop();         vis[T] = 0;         int Size = (int)V[T].size();         for(i=0; i<Size; i++){ int id = V[T][i].id; int w = V[T][i].w; if(dis[T]+w < dis[id]){     dis[id] = dis[T] + w;     if(!vis[id]){        Q.push(id);  vis[id] = 1;     } }         }    }    int ret = 0;    for(i=1; i<=n; i++) ret += dis[i];    return ret;}int main(){    int cas;    scanf("%d",&cas);    while(cas--){        int i;        scanf("%d%d",&n,&m);        for(i=0; i<m; i++) scanf("%d%d%d",x+i,y+i,z+i);        for(i=1; i<=n; i++) V[i].clear();        for(i=0; i<m; i++) V[x[i]].push_back(node(y[i],z[i]));        int ans1 = spfa();        for(i=1; i<=n; i++) V[i].clear();        for(i=0; i<m; i++) V[y[i]].push_back(node(x[i],z[i]));        int ans2 = spfa();        printf("%dn",ans1+ans2);    }    return 0;}