ng res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } inline void Out(long long a) //输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif long long T; //scanf("%lld",&T); T=Scan(); while(T--) { //scanf("%lld%lld",&N,&E); N=Scan(); E=Scan(); struct edge z,f; for(long long i=1;i<=E;i++)//建图部分 { long long a,b,v; //scanf("%lld%lld%lld",&a,&b,&v); a=Scan(); b=Scan(); v=Scan(); z.to=b;z.cost=v; f.to=a;f.cost=v; G[0][a].push_back(z); G[1][b].push_back(f); } //求最短路部分 SPFA(0); long long sum=0; for(long long i=2;i<=N;i++) sum+=dis[i]; SPFA(1); for(long long i=2;i<=N;i++) sum+=dis[i]; //printf("%lld\n",sum); Out(sum); putchar('\n'); memset(G,0,sizeof(G)); } }
?
/*太爽了，竟然弄出来了。优化了一下push_back，原来加结点是从头扫到尾巴的，现在多了一个指针记住尾巴*/
#include
#include
#include
#include
#include
#include
#include
using namespace std; struct edge{long long to,cost;}; const long long MAXN=1000001; const long long INF=(1<<30)-1; struct GRAPH//结构体 { struct edge e; GRAPH* next; GRAPH* pLast; int thefirst; void push_back(edge& add)//仿vector { if(thefirst) { pLast=this; thefirst=0; } pLast->next=new GRAPH; pLast=pLast->next; GRAPH addme; addme.e=add; *(pLast)=addme; } void clear() { next=0; pLast=this; } GRAPH()//一开始next指针一定要是0，G[v]是头结点，G[v]->next及其以后才存了边 { next=0; thefirst=1; //pLast=this;//此时这个GRAPH对象还没生成，这么用是错误的; } }G[2][MAXN]; long long N,E; bool visit[MAXN]; long long dis[MAXN]; long long que[MAXN]; inline void SPFA(long long kind)//0是正向，1是负向 { //memset(dis,INF,sizeof(long long)*(N+1); memset(visit,0,sizeof(bool)*(N+1)); fill(dis+1,dis+N+1,INF); // for(long long i=1;i<=N;i++) // { // dis[i]=(1<<30)-1; // } long long start=0; long long end=1; que[0]=1; dis[1]=0; while(start
dis[nowvert]+G[kind][nowvert][i].v) // { // if(!visit[to]) // { // que[end++]=to; // visit[to]=true; // } // dis[to]=dis[nowvert]+G[kind][nowvert][i].v; // } // } GRAPH* poin=&G[kind][nowvert]; poin=poin->next; while(poin) { edge e=poin->e; if(dis[e.to]>dis[nowvert]+e.cost) { if(!visit[e.to]) { que[end++]=e.to; visit[e.to]=true; } dis[e.to]=dis[nowvert]+e.cost; } poin=poin->next; } } } inline long long Scan() //输入外挂 { long long res=0,ch,flag=0; if((ch=getchar())=='-') flag=1; else if(ch>='0'&&ch<='9') res=ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return flag?-res:res; } inline void Out(long long a) //输出外挂 { if(a>9) Out(a/10); putchar(a%10+'0'); } int main() { #ifndef ONLINE_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif long long T; //scanf("%lld",&T); T=Scan(); while(T--) { //scanf("%lld%lld",&N,&E); N=Scan(); E=Scan(); struct edge z,f; for(long long i=1;i<=E;i++)//建图部分 { long long a,b,v; //scanf("%lld%lld%lld",&a,&b,&v); a=Scan(); b=Scan(); v=Scan(); z.to=b;z.cost=v; f.to=a;f.cost=v; G[0][a].push_back(z); G[1][b].push_back(f); } //求最短路部分 SPFA(0); long long sum=0; for(long long i=2;i<=N;i++) sum+=dis[i]; SPFA(1); for(long long i=2;i<=N;i++) sum+=dis[i]; //printf("%lld\n",sum); Out(sum); putchar('\n'); //memset(G,0,sizeof(G)); for(int i=0;i<2;i++) { for(int j=1;j<=N;j++) { G[i][j].clear(); } } } }
?