先从节点N广搜一边,确定每个点到N的最短距离d[1...N],

然后按到N的距离把节点分成各层,从第d[1]层开始,对每一层先求出本层到下一层的最小代价(字典序),然后由这个最小代价

求出下一层哪一个节点是可以(通过最优路径)到达的,进行标记.重复操作,知道第d[N] = 0层.遍历过程中直接输出即可.

附源代码:

1 //对图建立层的结构,然后分别处理每层即可   2 #include 
         
             3 #include 
          
              4 #include 
           
               5 #include 
            
                6 #include 
             
                 7 #include 
              
                8 #include 
               
                 9 #include 
                
                  10 11 12 13 14 using namespace std; 15 16 const int INF = INT_MAX; 17 18 typedef pair
                 
                   pii; 19 20 typedef struct edge 21 { 22 int t; 23 int e; 24 edge* next; 25 } edge; 26 27 typedef struct node 28 { 29 int t; 30 node* next; 31 } node; 32 33 node pool[400000]; 34 bool vis[110000]; 35 node* link[110000]; 36 edge g[1000000]; 37 edge* head[110000]; 38 int cnt; 39 int q[110000]; 40 41 int N, M; 42 int d[110000]; 43 int ans[110000]; 44 45 inline void add_edge(int s, int t, int e) 46 { 47 g[cnt].t = t; 48 g[cnt].e = e; 49 g[cnt].next = head[s]; 50 head[s] = &g[cnt++]; 51 52 g[cnt].t = s; 53 g[cnt].e = e; 54 g[cnt].next = head[t]; 55 head[t] = &g[cnt++]; 56 } 57 inline void add_link(int s, int t) 58 { 59 pool[cnt].t = t; 60 pool[cnt].next = link[s]; 61 link[s] = &pool[cnt++]; 62 } 63 64 void build() 65 { 66 // memset(head, 0, sizeof(head)); 67 // cnt = 0; 68 69 int s, t, e; 70 for(int i = 0; i < M; i++) 71 { 72 scanf("%d %d %d", &s, &t, &e); 73 add_edge(s, t, e); 74 } 75 } 76 void buildLink() 77 { 78 cnt = 0; 79 for(int i = 1; i <= N; i++) 80 add_link(d[1] - d[i], i); 81 82 } 83 84 int main() 85 { 86 87 // freopen("input.txt", "r", stdin); 88 89 scanf("%d %d", &N, &M); 90 build(); 91 memset(d, -1, sizeof(d)); 92 93 int s = 0, t = 0;; 94 d[N] = 0; 95 q[t++] = N; 96 97 while(s < t) 98 { 99 int u = q[s++]; 100 101 for(edge* p = head[u]; p; p = p->next) 102 { 103 if(-1 == d[p->t]) 104 { 105 d[p->t] = d[u] + 1; 106 q[t++] = p->t; 107 } 108 } 109 } 110 printf("%d\n", d[1]); 111 vis[1] = true; 112 buildLink(); 113 114 for(int i = 0; i < d[1]; i++) 115 { 116 int ans = INF; 117 for(node* p = link[i]; p; p = p->next) 118 { 119 if(vis[p->t]) 120 { 121 int x = p->t; 122 for(edge* tp = head[x]; tp; tp = tp->next) 123 { 124 if(d[x] - 1 == d[tp->t]) 125 ans = min(ans, tp->e); 126 } 127 } 128 } 129 if(i) 130 putchar(' '); 131 printf("%d", ans); 132 if(i == d[1] - 1) 133 break; 134 135 for(node* p = link[i]; p; p = p->next) 136 { 137 if(vis[p->t]) 138 { 139 int x = p->t; 140 for(edge* tp = head[x]; tp; tp = tp->next) 141 { 142 if(ans == tp->e && d[x] - 1 == d[tp->t]) 143 { 144 vis[tp->t] = true; 145 } 146 } 147 } 148 } 149 } 150 151 puts(""); 152 153 return 0; 154 }
                 
                
               
              
             
            
           
          
         

~~~