题目链接：

题目大意

　　略。

分析

　　注意！！！，此题只有一个源点，但有

多个汇点。

　　这题本质上是求源点到汇点字典序的带权最长路，从前往后求比较麻烦，我们可以考虑从后往前求，求每个节点到某个汇点的最长距离和字典序最小的后继节点。

　　为此可先求拓扑序列，然后从后往前遍历拓扑序列，并进行松弛操作（同时也可以解决多汇点问题，SPFA则不行）。

代码如下

1 #include 
       
          2 using namespace std;  3    4 #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);  5 #define Rep(i,n) for (int i = 0; i < (int)(n); ++i)  6 #define For(i,s,t) for (int i = (int)(s); i <= (int)(t); ++i)  7 #define rFor(i,t,s) for (int i = (int)(t); i >= (int)(s); --i)  8 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i)  9 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) 10 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 11 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 12   13 #define pr(x) cout << #x << " = " << x << "  " 14 #define prln(x) cout << #x << " = " << x << endl 15   16 #define LOWBIT(x) ((x)&(-x)) 17   18 #define ALL(x) x.begin(),x.end() 19 #define INS(x) inserter(x,x.begin()) 20 #define UNIQUE(x) x.erase(unique(x.begin(), x.end()), x.end()) 21 #define REMOVE(x, c) x.erase(remove(x.begin(), x.end(), c), x.end()); // 删去 x 中所有 c  22 #define TOLOWER(x) transform(x.begin(), x.end(), x.begin(),::tolower); 23 #define TOUPPER(x) transform(x.begin(), x.end(), x.begin(),::toupper); 24   25 #define ms0(a) memset(a,0,sizeof(a)) 26 #define msI(a) memset(a,0x3f,sizeof(a)) 27 #define msM(a) memset(a,-1,sizeof(a)) 28  29 #define MP make_pair 30 #define PB push_back 31 #define ft first 32 #define sd second 33   34 template
        
          35 istream &operator>>(istream &in, pair
         
           &p) { 36     in >> p.first >> p.second; 37     return in; 38 } 39   40 template
          
            41 istream &operator>>(istream &in, vector
           
             &v) { 42     for (auto &x: v) 43         in >> x; 44     return in; 45 } 46  47 template
            
              48 ostream &operator<<(ostream &out, vector
             
               &v) { 49 Rep(i, v.size()) out << v[i] << " \n"[i == v.size()]; 50 return out; 51 } 52 53 template
              
                54 ostream &operator<<(ostream &out, const std::pair
               
                 &p) { 55 out << "[" << p.first << ", " << p.second << "]" << "\n"; 56 return out; 57 } 58 59 inline int gc(){ 60 static const int BUF = 1e7; 61 static char buf[BUF], *bg = buf + BUF, *ed = bg; 62 63 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 64 return *bg++; 65 } 66 67 inline int ri(){ 68 int x = 0, f = 1, c = gc(); 69 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 70 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 71 return x*f; 72 } 73 74 template
                
                  75 inline string toString(T x) { 76 ostringstream sout; 77 sout << x; 78 return sout.str(); 79 } 80 81 inline int toInt(string s) { 82 int v; 83 istringstream sin(s); 84 sin >> v; 85 return v; 86 } 87 88 //min <= aim <= max 89 template
                 
                   90 inline bool BETWEEN(const T aim, const T min, const T max) { 91 return min <= aim && aim <= max; 92 } 93 94 typedef long long LL; 95 typedef unsigned long long uLL; 96 typedef vector< int > VI; 97 typedef vector< bool > VB; 98 typedef vector< char > VC; 99 typedef vector< double > VD;100 typedef vector< string > VS;101 typedef vector< LL > VL;102 typedef vector< VI > VVI;103 typedef vector< VB > VVB;104 typedef vector< VS > VVS;105 typedef vector< VL > VVL;106 typedef vector< VVI > VVVI;107 typedef vector< VVL > VVVL;108 typedef pair< int, int > PII;109 typedef pair< LL, LL > PLL;110 typedef pair< int, string > PIS;111 typedef pair< string, int > PSI;112 typedef pair< string, string > PSS;113 typedef pair< double, double > PDD;114 typedef vector< PII > VPII;115 typedef vector< PLL > VPLL;116 typedef vector< VPII > VVPII;117 typedef vector< VPLL > VVPLL;118 typedef vector< VS > VVS;119 typedef map< int, int > MII;120 typedef unordered_map< int, int > uMII;121 typedef map< LL, LL > MLL;122 typedef map< string, int > MSI;123 typedef map< int, string > MIS;124 typedef set< int > SI;125 typedef stack< int > SKI;126 typedef queue< int > QI;127 typedef priority_queue< int > PQIMax;128 typedef priority_queue< int, VI, greater< int > > PQIMin;129 const double EPS = 1e-8;130 const LL inf = 0x7fffffff;131 const LL infLL = 0x7fffffffffffffffLL;132 const LL mod = 1e9 + 7;133 const int maxN = 1e4 + 7;134 const LL ONE = 1;135 const LL evenBits = 0xaaaaaaaaaaaaaaaa;136 const LL oddBits = 0x5555555555555555;137 138 struct Edge{139 int from, to, w;140 int et, lt;141 };142 143 istream& operator>> (istream& in, Edge &x) {144 in >> x.from >> x.to >> x.w;145 return in;146 }147 148 struct Vertex{149 int in, out, value, nxt;150 VI next, prev;151 int et, lt;152 153 void clear() {154 value = in = out = 0;155 nxt = inf;156 next.clear();157 prev.clear();158 et = 0;159 lt = inf;160 }161 };162 163 int N, M, S, T;164 Vertex V[maxN];165 vector< Edge > E;166 VI topo, ans;167 168 void addEdge(Edge &x) {169 V[x.from].next.PB(E.size());170 V[x.to].prev.PB(E.size());171 ++V[x.to].in;172 ++V[x.from].out;173 E.PB(x);174 }175 176 void init() {177 For(i, 1, N) V[i].clear();178 E.clear();179 topo.clear();180 ans.clear();181 }182 183 void TopoSort() {184 SKI sk;185 For(i, 1, N) if(!V[i].in) sk.push(i);186 187 while(!sk.empty()) {188 int tmp = sk.top(); sk.pop();189 190 topo.PB(tmp);191 Rep(i, V[tmp].next.size()) {192 Edge &e = E[V[tmp].next[i]];193 if(!--V[e.to].in) sk.push(e.to); 194 }195 }196 }197 198 // 在拓扑排序的基础上松弛 199 inline void relax() {200 rFor(i, topo.size() - 1, 0) {201 Rep(j, V[topo[i]].prev.size()) {202 Edge &e = E[V[topo[i]].prev[j]];203 if(V[e.from].value < V[e.to].value + e.w || V[e.from].value == V[e.to].value + e.w && e.to < V[e.from].nxt) {204 V[e.from].value = V[e.to].value + e.w;205 V[e.from].nxt = e.to;206 }207 }208 }209 }210 211 int main(){212 //freopen("MyOutput.txt","w",stdout);213 //freopen("input.txt","r",stdin);214 INIT();215 while(cin >> N >> M) {216 init();217 For(i, 1, M) {218 Edge t;219 cin >> t;220 addEdge(t);221 }222 223 TopoSort();224 S = topo.front();225 T = topo.back();226 227 relax();228 229 int t = S;230 while(t != inf) {231 ans.PB(t);232 t = V[t].nxt;233 }234 235 cout << V[S].value << endl;236 Rep(i, ans.size() - 1) cout << ans[i] << " " << ans[i + 1] << endl;237 } 238 return 0;239 }