题目链接：http://acm.uestc.edu.cn/#/problem/show/1647

题意：给你一个全为0的01串，问你能否通过一系列的变换，得到全为1的01串。

解法：将每个01串看作一个点，每一个变换可以看作是一条有向边，现在问题可以转化
为找从“00..0”这个点到“11..1”这个点的最短路，那么可以使用Dijkstra来解决这个问题。
对于每个CFT，建一条有向边，从si指向ti，权值为ti。然后运行Dijkstra即可。
复杂度O(ElogV) ，边数为10^5.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000010;
const int maxm = 400010;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int n, m, edgecnt, head[maxn];
LL dis[maxn];
bool vis[maxn];
struct edge{
    int to, next;
    LL w;
    edge(){}
    edge(int to, LL w, int next):to(to),w(w),next(next){}
}E[maxm];
void init(){
    memset(head,-1,sizeof(head));
    edgecnt=0;
}
void add(int u, int v, LL w){
    E[edgecnt].to=v,E[edgecnt].w=w,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
int Get(char *s){
    int ret = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++){
        ret = ret*2 + (s[i]-'0');
    }
    return ret;
}
void Dij(){
    priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int>> >pq;
    memset(vis,0,sizeof(vis));
    for(int i = 0; i <= (1<<n); i++) dis[i]=inf;
    dis[0]=0;
    pq.push(make_pair(dis[0],0));
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];~i;i=E[i].next){
            int v = E[i].to;
            if(dis[v]>dis[u]+E[i].w){
                dis[v]=dis[u]+E[i].w;
                pq.push(make_pair(dis[v],v));
            }
        }
    }
}
char s1[30], s2[30];
LL x;
int main()
{
    scanf("%d %d", &n, &m);
    init();
    for(int i=1; i<=m; i++){
        scanf("%s%s%lld", s1, s2, &x);
        int u = Get(s1);
        int v = Get(s2);
        add(u, v, x);
    }
    Dij();
    int en = (1<<n)-1;
    if(dis[en]==inf){
        printf("-1\n");
    }
    else{
        printf("%lld\n", dis[en]);
    }
    return 0;
}