題意：
? ? ?有一個骨牌游戲，就是推到一個后所有的牌都會被退到的那種游戲，起點是1，有兩種骨牌，一種是關鍵牌，另一種是普通牌，普通牌是連接關鍵牌用的，給你一些邊a b c的意思是關鍵牌a倒之后c時間b會被a的效應影響到，被推倒，然后問題是求出所有牌被都被推倒的時間，還有最后倒的牌處在的位置（兩種情況，處在某一個關鍵牌上，處在某一條關鍵牌之間）。


思路：
? ? ? 可以用spfa或者是bfs啥的來做，我用的是spfa跑一遍最短路，跑完之后把所有到1節點的距離的最大的那個拿出來a，這個值有什么用？想下，假如最后倒下的骨牌是一個關鍵骨牌，那么是不是倒下的時間是這個值，到小的牌就是這個點，那么其他情況呢？也很好解決，我的想法是標記所有最短路上的邊（不是單獨一條路徑，可以充當最短路上的邊的邊都行），那么這些邊肯定可以再a時間內到達，其他的邊就不一定了，所有枚舉所有非最短路邊，然后算出如果在當前路徑上相遇的時間會是多少？邊a b c 的話相遇時間是(dis[a]+dis[b]+c) / 2,如果比最短路的最長那個值還大，那么就更新最優，并且記錄當前的這兩個端點ab,如果所有的非最短路上的邊，都沒有更新值，也就是時間都比一開始那個最短的最長小，那么最后就是落在了唯一的一個特殊牌上了，具體細節可以看下下面代碼。




#include<queue>
#include<stdio.h>
#include<string.h>


#define N_node 500 + 5
#define N_edge 500000 + 100
#define INF 1000000000


using namespace std;


typedef struct
{
? ? int to ,next ,cost;
}STAR;


typedef struct
{
? ? int a ,b ,c;
}EDGE;


STAR E[N_edge];
EDGE edge[N_edge];
int list[N_node] ,tot;
int s_x[N_node] ,mark[N_node];


void add(int a ,int b ,int c)
{
? ? E[++tot].to = b;
? ? E[tot].cost = c;
? ? E[tot].next = list[a];
? ? list[a] = tot;
}


void Spfa(int s ,int n)
{
? ? memset(mark ,0 ,sizeof(mark));
? ? for(int i = 0 ;i <= n ;i ++)
? ? s_x[i] = INF;
? ? queue<int>q;
? ? q.push(s);
? ? mark[s] = 1;
? ? s_x[s] = 0;
? ? while(!q.empty())
? ? {
? ? ? ? int xin ,tou;
? ? ? ? tou = q.front();
? ? ? ? q.pop();
? ? ? ? mark[tou] = 0;
? ? ? ? for(int k = list[tou] ;k ;k = E[k].next)
? ? ? ? {
? ? ? ? ? ? xin = E[k].to;
? ? ? ? ? ? if(s_x[xin] > s_x[tou] + E[k].cost)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s_x[xin] = s_x[tou] + E[k].cost;
? ? ? ? ? ? ? ? if(!mark[xin])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mark[xin] = 1;
? ? ? ? ? ? ? ? ? ? q.push(xin);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return ;
}


int main ()
{
? ? int n ,m ,a ,b ,c ,i;
? ? int cas = 1;
? ? while(~scanf("%d %d" ,&n ,&m) && n + m)
? ? {
? ? ? ? memset(list ,0 ,sizeof(list));
? ? ? ? tot = 1;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d %d" ,&a ,&b ,&c);
? ? ? ? ? ? add(a ,b ,c);
? ? ? ? ? ? add(b ,a ,c);
? ? ? ? ? ? edge[i].a = a;
? ? ? ? ? ? edge[i].b = b;
? ? ? ? ? ? edge[i].c = c;
? ? ? ? }
? ? ? ? printf("System #%d\n" ,cas ++);
? ? ? ? if(n == 1 && m == 0)
? ? ? ? {
? ? ? ? ? ? printf("The last domino falls after 0.0 seconds, at key domino 1.\n\n");
? ? ? ? ? ? continue;


? ? ? ? }


? ? ? ? Spfa(1 ,n);
? ? ? ? double time = 0 ,maxt = 0;
? ? ? ? int maxid;
? ? ? ? for(i = 2 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? if(maxt < s_x[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? maxt = s_x[i] * 1.0;
? ? ? ? ? ? ? ? maxid = i;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? time = maxt;
? ? ? ? int aa = 0 ,bb = 0;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? a = edge[i].a ,b = edge[i].b ,c = edge[i].c;
? ? ? ? ? ? if(s_x[a] + c != s_x[b] && s_x[b] + c != s_x[a])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? double tmp = (s_x[a] + s_x[b] + c) / 2.0;
? ? ? ? ? ? ? ? if(time < tmp)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? time = tmp;
? ? ? ? ? ? ? ? ? ? aa = a ,bb = b;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }


? ? ? ? printf("The last domino falls after %.1lf seconds, " ,time);
? ? ? ? a = aa < bb ? aa : bb;
? ? ? ? b = aa > bb ? aa : bb;
? ? ? ? if(maxt == time) printf("at key domino %d.\n\n" ,maxid);
? ? ? ? else printf("between key dominoes %d and %d.\n\n" ,a ,b);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ1135比较有意思的对短路（多米骨牌）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。