求來回最短路加起來最長的一條。
兩次SPFA,然後選某個點的來回最長。(有向圖)
Dijkstra+鄰接矩陣 比較方便建立 反向圖。
我用SPFA+2個鄰接表(正圖+反圖),C++ 32ms。
#include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-6 using namespace std; int n,m,start; struct lx { int v,t; }; vectorg1[1001]; vectorg2[1001]; int dis1[1001]; int dis2[1001]; void SPFA(int *dis,vectorg[]) { bool vis[1001]; queueq; for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=0; vis[start]=1,dis[start]=0; q.push(start); while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int j=0;jdis[u]+t) { dis[v]=dis[u]+t; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { while(scanf("%d%d%d",&n,&m,&start)!=EOF) { for(int i=1;i<=n;i++) g1[i].clear(),g2[i].clear(); while(m--) { int u,v,t; scanf("%d%d%d",&u,&v,&t); lx now; now.v=v,now.t=t; g1[u].push_back(now); now.v=u; g2[v].push_back(now); } SPFA(dis1,g1); SPFA(dis2,g2); int ans=0; for(int i=1;i<=n;i++) ans=max(ans,dis1[i]+dis2[i]); printf("%d\n",ans); } }
<基於Qt與POSIX線程>多線程下載器的簡易搭
由於本人也是初學,難免有錯誤,請大家諒解。特別
hdu 5652 India and China Origi
LA 6801 Sequence(DP) 6
Prime Ring
COCOS2D-X中UI動畫導致閃退與UI動畫淺析,coco