從2：30PM到10：30PM，做了好久啊，先用dij+heap沒弄出來，後來一找題解，都是SPFA，那個用兩個數組維護圖的還真是很贊，，，雖然看了很久，然後用了個例子比劃比劃就好了。
本來自己寫的鄰接表TLE超時很沮喪，然後就照著題解的思路往下做了，用倆數組維護圖+SPFA，開上IO掛，A了，1000ms（題目要求8000ms）
後來試了試vector果然慢得不行，意料之中
然後又回頭看看自己寫的鄰接表，猛地發現，push_back這個寫法有點2，我是從頭結點遍歷到尾巴，然後再在尾巴插入結點，改成用一個指針記住尾巴的位置，插完結點後，更新尾巴的位置就好了，把問題復雜度由O(n)變為O(1)
好吧，先就這樣，A其他題目了，有空看看dij+heap怎麼弄
這次的注釋還是蠻多的
/*照題解的AC代碼，這裡用來保存圖的link last兩個數組竟然不用清空，實是不錯*/
#include
#include
#include
#include
#include
#include
using namespace std;
long long N,E;
const long long MAXN=1000001;
const long long INF=(1<<27)-1;
bool visit[MAXN];
long long dis[MAXN];
long long que[MAXN];
struct eg
{
long long to,v,pre;
}link[2][MAXN];
long long last[2][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<<31)-1;
}
long long start=0;
long long end=1;
que[0]=1;
dis[1]=0;
long long nowedge;
while(startdis[nowvert]+link[kind][nowedge].v)
{
if(!visit[to])
{
que[end++]=to;
visit[to]=true;
}
dis[to]=dis[nowvert]+link[kind][nowedge].v;
}
nowedge=link[kind][nowedge].pre;//這裡要記得按鏈條轉移nowedge哦
}
}
}
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();
memset(last,-1,sizeof(last));
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();
link[0][i].to=b;
link[0][i].v=v;
link[0][i].pre=last[0][a];//last點記錄著加入當前邊之前的從a點出來的最後一條邊的編號，作為這條邊的前驅
last[0][a]=i;//相應的，當前邊就是最後一個出現的從a點出來的邊，記錄下這個邊的序號
link[1][i].to=a;
link[1][i].v=v;
link[1][i].pre=last[1][b];
last[1][b]=i;
}
//求最短路部分
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');
}
}
/*bug點：
long long
dis[1]=0
visit的更新
*/
/*用vector，超時了，主要是點還是太多了，有差不多一百萬個，雖然給了8秒，雖然用了OI掛，本地測試，也就6條邊，都要0.8秒，確實不行。學長說STL適用於大概1W的，天。。。*/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct node
{
long long to,v;
};
long long N,E;
const long long MAXN=1000001;
const long long INF=(1<<27)-1;
bool visit[MAXN];
long long dis[MAXN];
long long que[MAXN];
vectorG[2][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<<31)-1;
}
long long start=0;
long long end=1;
que[0]=1;
dis[1]=0;
while(startdis[nowvert]+G[kind][nowvert][i].v)
{
if(!visit[to])
{
que[end++]=to;
visit[to]=true;
}
dis[to]=dis[nowvert]+G[kind][nowvert][i].v;
}
}
}
}
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 node 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.v=v;
f.to=a;f.v=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');
for(int i=0;i<2;i++)
{
for(int j=1;j<=N;j++)
{
G[i][j].clear();
}
}
}
}
/*這是我自己寫的鄰接表，也TLE了，很憤憤不平，很想知道這個到底為什麼慢*/
#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;
void push_back(edge add)//仿vector
{
GRAPH* poin=this;
while(poin->next)
{
poin=poin->next;
}
GRAPH addme;
addme.e=add;
poin->next=new GRAPH;
*(poin->next)=addme;
}
GRAPH()//一開始next指針一定要是0，G[v]是頭結點，G[v]->next及其以後才存了邊
{
next=0;
}
}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(startdis[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));
}
}
/*太爽了，竟然弄出來了。優化了一下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(startdis[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();
}
}
}
}
